题目描述
一棵 nn 个点的树，每个点的初始权值为 11。
对于这棵树有 qq 个操作，每个操作为以下四种操作之一：
-
+ u v c：将 uu 到 vv 的路径上的点的权值都加上自然数 cc； -
- u1 v1 u2 v2：将树中原有的边 (u_1,v_1)(u1,v1) 删除，加入一条新边 (u_2,v_2)(u2,v2)，保证操作完之后仍然是一棵树； -
* u v c：将 uu 到 vv 的路径上的点的权值都乘上自然数 cc； -
/ u v：询问 uu 到 vv 的路径上的点的权值和，将答案对 5106151061 取模。
输入格式
第一行两个整数 n,qn,q
接下来 n-1n−1 行每行两个正整数 u,vu,v，描述这棵树的每条边。
接下来 qq 行，每行描述一个操作。
输出格式
对于每个询问操作，输出一行一个整数表示答案。
#include<bits/stdc++.h> using namespace std; const int maxn=1e6+100; const int mod=51061; typedef long long ll; ll f[maxn]; ll ch[maxn][2]; ll v[maxn]; ll size[maxn]; ll lm[maxn]; ll la[maxn]; ll s[maxn]; ll st[maxn]; bool r[maxn]; bool nroot (int x) { return ch[f[x]][0]==x||ch[f[x]][1]==x; } void pushup (int x) { s[x]=s[ch[x][0]]+s[ch[x][1]]+v[x]; s[x]%=mod; size[x]=size[ch[x][0]]+size[ch[x][1]]+1; } void rev (int x) { //翻转 int t=ch[x][0]; ch[x][0]=ch[x][1]; ch[x][1]=t; r[x]^=1; } void push_mul (int x,int c) { //乘 s[x]*=c;s[x]%=mod; v[x]*=c;v[x]%=mod; lm[x]*=c;lm[x]%=mod; la[x]*=c;la[x]%=mod; } void push_add (int x,int c) { //加 s[x]+=c*size[x];s[x]%=mod; v[x]+=c;v[x]%=mod; la[x]+=c;la[x]%=mod; } void pushdown (int x) { if (lm[x]!=1) push_mul(ch[x][0],lm[x]),push_mul(ch[x][1],lm[x]),lm[x]=1; if (la[x]) push_add(ch[x][0],la[x]),push_add(ch[x][1],la[x]),la[x]=0; if (r[x]) { if (ch[x][0]) rev(ch[x][0]); if (ch[x][1]) rev(ch[x][1]); r[x]=0; } } void rotate (int x) { int y=f[x],z=f[y],k=ch[y][1]==x,w=ch[x][!k]; if (nroot(y)) ch[z][ch[z][1]==y]=x; ch[x][!k]=y; ch[y][k]=w; if (w) f[w]=y; f[y]=x;f[x]=z; pushup(y); } void splay (int x) { int 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((ch[y][0]==x)^(ch[z][0]==y)?x:y); rotate(x); } pushup(x); } void access (int x) { for (int y=0;x;x=f[y=x]) splay(x),ch[x][1]=y,pushup(x); } void makeroot(int x) { access(x); splay(x); rev(x); } void split (int x,int y) { makeroot(x); access(y); splay(y); } void link (int x,int y) { makeroot(x); f[x]=y; } void cut (int x,int y) { split(x,y); f[x]=ch[y][0]=0; } int n,q; int main () { scanf("%d%d",&n,&q); for (int i=1;i<=n;i++) v[i]=size[i]=lm[i]=1; for (int i=1;i<n;i++) { int x,y; scanf("%d%d",&x,&y); link(x,y); } while (q--) { string op; cin>>op; if (op=="+") { int a,b,k; scanf("%d%d%d",&a,&b,&k); split(a,b); push_add(b,k); } else if (op=="-") { int a,b; scanf("%d%d",&a,&b);cut(a,b); scanf("%d%d",&a,&b);link(a,b); } else if (op=="*") { int a,b,k; scanf("%d%d%d",&a,&b,&k); split(a,b); push_mul(b,k); } else if (op=="/") { int a,b; scanf("%d%d",&a,&b); split(a,b); printf("%lld ",s[b]%mod); } } }