Description

 一棵n个点的树,每个点的初始权值为1。对于这棵树有q个操作,每个操作为以下四种操作之一:

  • u v c:将u到v的路径上的点的权值都加上自然数c;
  • u1 v1 u2 v2:将树中原有的边(u1,v1)删除,加入一条新边(u2,v2),保证操作完之后仍然是一棵树;
  • u v c:将u到v的路径上的点的权值都乘上自然数c;
    / u v:询问u到v的路径上的点的权值和,求出答案对于51061的余数。

Input

第一行两个整数n,q
接下来n-1行每行两个正整数u,v,描述这棵树
接下来q行,每行描述一个操作

Output

对于每个/对应的答案输出一行

Sample Input

3 2
1 2
2 3
* 1 3 4
/ 1 1

Sample Output

4

Hint

数据规模和约定

10%的数据保证,1<=n,q<=2000

另外15%的数据保证,1<=n,q<=5*10^4,没有-操作,并且初始树为一条链

另外35%的数据保证,1<=n,q<=5*10^4,没有-操作

100%的数据保证,1<=n,q<=10^5,0<=c<=10^4

Solve

理解了lct的本质其实就是道板子题,注意乘优先级高于加,类似于luogu的那道线段树题,然后sum维护等跟线段树差不多,维护一个sz即可,不同之处在于要同时对每个点的val进行实时修改,还是很方便的qwq

Code:

#include<bits/stdc++.h>
#define maxn 100005
using namespace std;
typedef long long ll;
const ll mod=51061;
int rev[maxn],ch[maxn][2],fa[maxn],st[maxn],top;
ll val[maxn],sum[maxn],sz[maxn],add[maxn],mul[maxn];
bool check(int x){return ch[fa[x]][1]==x;}
void link(int x,int y,bool kind){
    fa[x]=y;ch[y][kind]=x;
}
bool nroot(int x){return ch[fa[x]][1]==x||ch[fa[x]][0]==x;}
void upload(int now){
    sz[now]=sz[ch[now][0]]+sz[ch[now][1]]+1ll;
    sum[now]=(sum[ch[now][0]]+sum[ch[now][1]]+val[now])%mod;
}
void download(int x){
    if(rev[x]){
        swap(ch[x][0],ch[x][1]);
        rev[ch[x][0]]^=1;rev[ch[x][1]]^=1;
        rev[x]=0;
    }
    if(mul[x]!=1||add[x]!=0){
        int lc=ch[x][0],rc=ch[x][1];
        val[lc]=(val[lc]*mul[x]%mod+add[x])%mod;
        val[rc]=(val[rc]*mul[x]%mod+add[x])%mod;
        sum[lc]=(sum[lc]*mul[x]%mod+add[x]*sz[lc]%mod)%mod;
        sum[rc]=(sum[rc]*mul[x]%mod+add[x]*sz[rc]%mod)%mod;
        mul[lc]=mul[lc]*mul[x]%mod;
        mul[rc]=mul[rc]*mul[x]%mod;
        add[lc]=(add[lc]*mul[x]%mod+add[x])%mod;
        add[rc]=(add[rc]*mul[x]%mod+add[x])%mod;
        mul[x]=1;add[x]=0;
    }
}
void rotate(int x){
    int y=fa[x],z=fa[y];
    bool kind=check(x);
    int k=ch[x][!kind];
    link(k,y,kind);
    if(nroot(y)) link(x,z,check(y));fa[x]=z;
    link(y,x,!kind);
    upload(y);upload(x);
}
void splay(int x){
    top=0;
    int y=x;st[++top]=y;
    while(nroot(y)) st[++top]=fa[y],y=fa[y];
    while(top) download(st[top--]);
    while(nroot(x)){
        y=fa[x];
        if(nroot(y)) check(y)^check(x)?rotate(x):rotate(y);
        rotate(x);
    }
    upload(x);
}
void access(int x){
    for(int y=0;x;y=x,x=fa[x])
     splay(x),ch[x][1]=y,upload(x);
}
void makeroot(int x){
    access(x);
    splay(x);
    rev[x]^=1;download(x);
}
void split(int x,int y){
    makeroot(x);
    access(y);
    splay(y);
}
int findroot(int x){
    access(x);splay(x);
    while(ch[x][0]) download(x),x=ch[x][0];//记得下传 
    splay(x);return x; 
}
void link(int x,int y){//要保证当前splay顶点连边才行 
    makeroot(x);
    if(findroot(y)==x) return;
    fa[x]=y;
}
void cut(int x,int y){
    makeroot(x);
    if(findroot(y)!=x||ch[y][0]||fa[y]!=x) return;
    ch[x][1]=fa[y]=0;upload(x);//结合深度最小性质思考 
}
int n,q,x,y;
char op[5];
ll z;
void init(){
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++) mul[i]=val[i]=sz[i]=1;//初始值 
    for(int i=1;i<n;i++){
        scanf("%d%d",&x,&y);
        link(x,y);
    }
    for(int i=1;i<=q;i++){
        scanf("%s",op);
        if(op[0]=='+'){
            scanf("%d%d%lld",&x,&y,&z);
            split(x,y);
            val[y]=(val[y]+z)%mod;
            sum[y]=(sum[y]+z*sz[y]%mod)%mod;
            add[y]=(add[y]+z)%mod;
        }
        else if(op[0]=='-'){
            int a,b,c,d;
            scanf("%d%d%d%d",&a,&b,&c,&d);
            cut(a,b);
            link(c,d);
        }
        else if(op[0]=='*'){
            scanf("%d%d%lld",&x,&y,&z);
            split(x,y);
            val[y]=val[y]*z%mod;
            sum[y]=(sum[y]*z)%mod;
            add[y]=add[y]*z%mod;
            mul[y]=mul[y]*z%mod;
        }
        else if(op[0]=='/'){
            scanf("%d%d",&x,&y);
            split(x,y);printf("%lld\n",sum[y]);
        }
    }
}
int main(){
    init();
    
    return 0;
}
Last modification:April 3rd, 2019 at 10:52 am