题目描述

一棵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的余数。

输入输出格式

输入格式：

 

第一行两个整数n，q

接下来n-1行每行两个正整数u，v，描述这棵树

接下来q行，每行描述一个操作

 

输出格式：

 

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

 

输入输出样例

输入样例#1：

3 21 22 3* 1 3 4/ 1 1

输出样例#1：

4

说明

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

 

题解

一起膜拜%%%

不知道为什么我的LCT板子好像各种有问题……和大佬的各种操作兼容不起来……然后也不知道要怎么改……

总之就是在树上打上各种标记，然后向线段树一样记得下传……

然后各种细节我一个都没考虑到……多亏了大佬的提醒orz

1 //minamoto 2 #include
     
       3 #define int unsigned int 4 #define mod 51061 5 using namespace std; 6 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 7 char buf[1<<21],*p1=buf,*p2=buf; 8 inline int read(){ 9     #define num ch-'0'10     char ch;bool flag=0;int res;11     while(!isdigit(ch=getc()))12     (ch=='-')&&(flag=true);13     for(res=num;isdigit(ch=getc());res=res*10+num);14     (flag)&&(res=-res);15     #undef num16     return res;17 }18 const int N=100005;19 int n,fa[N],ch[N][2],v[N],sum[N],sz[N],tmul[N],tadd[N],s[N],top,rev[N];20 bool isroot(int x){
   return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;}21 void pushup(int x){22     sum[x]=(sum[ch[x][0]]+sum[ch[x][1]]+v[x])%mod;23     sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+1;24 }25 void pushrev(int x){26     swap(ch[x][0],ch[x][1]);rev[x]^=1;27 }28 #define mul(x) x*=c,x%=mod29 #define add(x,c) x+=c,x%=mod30 void pushmul(int x,int c){31     mul(sum[x]),mul(v[x]),mul(tmul[x]),mul(tadd[x]);32 }33 void pushadd(int x,int c){34     add(sum[x],c*sz[x]),add(v[x],c),add(tadd[x],c);35 }36 #undef mul37 #undef add38 void pushdown(int x){39     if(tmul[x]!=1) pushmul(ch[x][0],tmul[x]),pushmul(ch[x][1],tmul[x]),tmul[x]=1;40     if(tadd[x]) pushadd(ch[x][0],tadd[x]),pushadd(ch[x][1],tadd[x]),tadd[x]=0;41     if(rev[x]) {
   if(ch[x][0]) pushrev(ch[x][0]);if(ch[x][1]) pushrev(ch[x][1]);rev[x]=0;}42 }43 void rotate(int x){44     int y=fa[x],z=fa[y],d=(ch[y][1]==x);if(!isroot(y)) ch[z][ch[z][1]==y]=x;45     fa[x]=z,fa[y]=x;fa[ch[x][d^1]]=y,ch[y][d]=ch[x][d^1],ch[x][d^1]=y;pushup(y),pushup(x);46 }47 void splay(int x){48     s[top=1]=x;for(int i=x;!isroot(i);i=fa[i]) s[++top]=fa[i];for(int i=top;i>=1;--i) pushdown(s[i]);49     for(int y=fa[x],z=fa[y];!isroot(x);y=fa[x],z=fa[y]){50         if(!isroot(y)) ((ch[z][1]==y)^(ch[y][1]==x))?rotate(x):rotate(y);rotate(x);51     }52 }53 void access(int x){
   int t=0;while(x){splay(x),ch[x][1]=t,pushup(x),t=x,x=fa[x];}}54 void makeroot(int x){access(x),splay(x),pushrev(x);}55 int findroot(int x){access(x);splay(x);pushdown(x);while(ch[x][0]) pushdown(x=ch[x][0]);return x;}56 void split(int x,int y){makeroot(x),access(y),splay(y);}57 void link(int x,int y){makeroot(x),fa[x]=y;}58 void cut(int x,int y){split(x,y),fa[x]=ch[y][0]=0;}59 #undef int60 int main(){61     //freopen("testdata.in","r",stdin);62     int n,q;63     n=read(),q=read();64     for(int i=1;i<=n;++i) tmul[i]=sz[i]=v[i]=1;65     for(int i=1;i