Tsinsen A1303. tree(伍一鸣) (LCT+处理标记)

时间:2021-01-01 15:58:30

【题目链接】

http://www.tsinsen.com/A1303

【题意】

给定一棵树,提供树上路径乘/加一个数,加边断边,查询路径和的操作。

【思路】

LCT+传标

一次dfs构造LCT。

LCT维护信息:v,sum,rev,add,mul,siz

提取路径(u,v):evert(u)->Access(v),splay(v),此时以v为根的splay辅助树即u->v的路径,直接进行操作即可。

关于下传标记:

Hezecong神犇的总结

对于一个节点的标记,始终保持该标记已作用在该节点上。

  给节点打标记后作用于该节点,每次传标,给儿子打上标记且作用于该儿子。

对于覆盖类标记,直接覆盖即可。反转标记单独处理。

  对于非覆盖类标记,考虑操作先后:先下传乘法标记,然后下传加法标记。对于乘法下传,还需要作用在加法标记上。

【代码】

 #include<cstdio>
#include<cstring>
#include<iostream>
#define FOR(a,b,c) for(int a=b;a<=c;a++)
#define trav(u,i) for(int i=front[u];i;i=e[i].nxt)
using namespace std; typedef long long ll;
typedef unsigned int ul;
const int N = 4e5+;
const int MOD = ; namespace LCT { struct Node {
Node *ch[],*fa;
ul v,siz,rev,add,mul,sum;
Node() ;
//给当前结点打上标记 且更新当前结点
void mulv(int x) {
mul=(mul*x)%MOD;
v=(v*x)%MOD;
add=(add*x)%MOD;
sum=(sum*x)%MOD;
}
void addv(int x) {
v=(v+x)%MOD;
add=(add+x)%MOD;
sum=(sum+siz*x)%MOD;
}
void reverse() {
rev^=;
swap(ch[],ch[]);
}
//up push down
void up_push() {
if(fa->ch[]==this||fa->ch[]==this)
fa->up_push();
if(mul^) { //mul != 1
ch[]->mulv(mul);
ch[]->mulv(mul);
mul=;
}
if(add) {
ch[]->addv(add);
ch[]->addv(add);
add=;
}
if(rev) {
ch[]->reverse();
ch[]->reverse();
rev=;
}
}
void maintain() {
siz=ch[]->siz+ch[]->siz+;
sum=(ch[]->sum+ch[]->sum+v)%MOD;
}
} *null=new Node, T[N];
Node:: Node() {
fa=ch[]=ch[]=null;
add=rev=,mul=siz=;
sum=v=;
} void rot(Node* o,int d) {
Node *p=o->fa;
p->ch[d]=o->ch[d^];
o->ch[d^]->fa=p;
o->ch[d^]=p;
o->fa=p->fa;
if(p==p->fa->ch[])
p->fa->ch[]=o;
else if(p==p->fa->ch[])
p->fa->ch[]=o;
p->fa=o;
p->maintain();
}
void splay(Node* o) {
o->up_push();
Node *nf,*nff;
while(o->fa->ch[]==o||o->fa->ch[]==o) {
nf=o->fa,nff=nf->fa;
if(o==nf->ch[]) {
if(nf==nff->ch[]) rot(nf,);
rot(o,);
} else {
if(nf==nff->ch[]) rot(nf,);
rot(o,);
}
}
o->maintain();
}
void Access(Node* o) {
Node* son=null;
while(o!=null) {
splay(o);
o->ch[]=son;
o->maintain();
son=o; o=o->fa;
}
}
void evert(Node* o) {
Access(o);
splay(o);
o->reverse();
}
void Link(Node *u,Node *v) {
evert(u);
u->fa=v;
}
void Cut(Node *u,Node *v) {
evert(u);
Access(v); splay(v);
u->fa=v->ch[]=null;
v->maintain();
} }
using namespace LCT; struct Edge { int v,nxt;
}e[N<<];
int en=,front[N];
void adde(int u,int v) {
e[++en]=(Edge){v,front[u]}; front[u]=en;
} ll read()
{
char c=getchar();
ll f=,x=;
while(!isdigit(c)) {
if(c=='-') f=-;
c=getchar();
}
while(isdigit(c))
x=x*+c-'',
c=getchar();
return x*f;
} int n,q; void build(int u,int fa) {
T[u].sum=T[u].v=;
trav(u,i) {
int v=e[i].v;
if(v!=fa) {
T[v].fa=&T[u];
build(v,u);
}
}
} int main()
{
null->siz=null->mul=;
n=read(),q=read();
for(int i=;i<n;i++) {
int u=read(),v=read();
adde(u,v),adde(v,u);
}
build(,-);
char op[];
int u,v,x,y;
while(q--) {
scanf("%s",&op);
u=read(),v=read();
if(op[]=='+' || op[]=='*') {
x=read();
evert(&T[u]);
Access(&T[v]); splay(&T[v]);
if(op[]=='+') T[v].addv(x);
else T[v].mulv(x);
} else
if(op[]=='-') {
x=read(),y=read();
Cut(&T[u],&T[v]);
Link(&T[x],&T[y]);
} else {
evert(&T[u]);
Access(&T[v]); splay(&T[v]);
printf("%d\n",T[v].sum);
}
}
return ;
}