一道洛谷的题目，来康康

Question

题目描述
一棵 nn 个点的树，每个点的初始权值为 11。
对于这棵树有 qq 个操作，每个操作为以下四种操作之一：

• u v c：将 uu 到 vv 的路径上的点的权值都加上自然数 cc；

• u1 v1 u2 v2：将树中原有的边 (u_1,v_1)(u
  1
  ​
  ,v
  1
  ​
  ) 删除，加入一条新边 (u_2,v_2)(u
  2
  ​
  ,v
  2
  ​
  )，保证操作完之后仍然是一棵树；

• u v c：将 uu 到 vv 的路径上的点的权值都乘上自然数 cc；

/ u v：询问 uu 到 vv 的路径上的点的权值和，将答案对 5106151061 取模。

输入格式
第一行两个整数 n,qn,q

接下来 n-1n−1 行每行两个正整数 u,vu,v，描述这棵树的每条边。

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

输出格式
对于每个询问操作，输出一行一个整数表示答案。

输入输出样例
输入 #1复制
3 2
1 2
2 3

• 1 3 4
  / 1 1
  输出 #1复制
  4
  说明/提示
  【数据范围】
  对于 10%10% 的数据，1\le n,q \le 20001≤n,q≤2000；
  另有 15%15% 的数据，1 \le n,q \le 5\times 10^41≤n,q≤5×10
  4
  ，没有 - 操作，并且初始树为一条链；
  另有 35%35% 的数据，1 \le n,q \le 5\times 10^41≤n,q≤5×10
  4
  ，没有 - 操作；
  对于 100%100% 的数据，1\le n,q \le 10^51≤n,q≤10
  5
  ，0\le c \le 10^40≤c≤10
  4
  。

Answer 1

LCT啊，我会了

#include<cstdio>
#include<cstdlib>
#define R register unsigned int
#define I inline
#define YL 51061
#define lc c[x][0]
#define rc c[x][1]
#define mul(x) x*=c;x%=YL
#define add(x,c) x+=c;x%=YL
#define G ch=getchar()
#define gc G;while(ch<'*')G
#define in(z) gc;z=ch&15;G;while(ch>'*')z*=10,z+=ch&15,G;
const int N=100009;
unsigned int n,f[N],c[N][2],v[N],s[N],sz[N],lm[N],la[N],st[N];
bool r[N];
I bool nroot(R x){//好像Dalao都写的是isroot
    return c[f[x]][0]==x||c[f[x]][1]==x;
}
I void pushup(R x){
    s[x]=(s[lc]+s[rc]+v[x])%YL;
    sz[x]=sz[lc]+sz[rc]+1;
}
I void pushr(R x){//翻转
    R t=lc;lc=rc;rc=t;r[x]^=1;
}
I void pushm(R x,R c){//乘
    mul(s[x]);mul(v[x]);mul(lm[x]);mul(la[x]);
}
I void pusha(R x,R c){//加
    add(s[x],c*sz[x]);add(v[x],c);add(la[x],c);
}
I void pushdown(R x){
    if(lm[x]!=1)pushm(lc,lm[x]),pushm(rc,lm[x]),lm[x]=1;
    if(la[x])   pusha(lc,la[x]),pusha(rc,la[x]),la[x]=0;
    if(r[x])   {if(lc)pushr(lc);if(rc)pushr(rc);r[x]=0;}
}
I void rotate(R x){
    R y=f[x],z=f[y],k=c[y][1]==x,w=c[x][!k];
    if(nroot(y))c[z][c[z][1]==y]=x;c[x][!k]=y;c[y][k]=w;//注意if(nroot(y))，本蒟蒻经常忘写
    if(w)f[w]=y;f[y]=x;f[x]=z;
    pushup(y);
}
I void splay(R x){
    R y=x,z=0;
    st[++z]=y;//手动放个栈
    while(nroot(y))st[++z]=y=f[y];
    while(z)pushdown(st[z--]);
    while(nroot(x)){
        y=f[x];z=f[y];
        if(nroot(y))
            rotate((c[y][0]==x)^(c[z][0]==y)?x:y);
        rotate(x);
    }
    pushup(x);
}
I void access(R x){
    for(R y=0;x;x=f[y=x])
        splay(x),rc=y,pushup(x);
}
I void makeroot(R x){
    access(x);
    splay(x);
    pushr(x);
}
I void split(R x,R y){
    makeroot(x);
    access(y);
    splay(y);
}
I void link(R x,R y){
    makeroot(x);f[x]=y;
}
I void cut(R x,R y){
    split(x,y);f[x]=c[y][0]=0;
}
int main()
{
    register char ch;
    R q,i,a,b,k;
    in(n);in(q);
    for(i=1;i<=n;++i)v[i]=sz[i]=lm[i]=1;//注意乘法标记的初值为1
    for(i=1;i<n;++i){
        in(a);in(b);
        link(a,b);
    }
    while(q--){
        gc;
        switch(ch){
        case '+':
            in(a);in(b);in(k);
            split(a,b);pusha(b,k);
            break;
        case '-':
            in(a);in(b);cut(a,b);
            in(a);in(b);link(a,b);
            break;
        case '*':
            in(a);in(b);in(k);
            split(a,b);pushm(b,k);
            break;
        case '/':
            in(a);in(b);
            split(a,b);
            printf("%d\n",s[b]);
        }
    }
    return 0;
}