P1501 [国家集训队] Tree II
大意
动态维护树上的乘积和加和。
思路
直接 \(\text{LCT}\) 维护即可，但是注意乘法和加法的混合的下传。
代码
#include<iostream>
using namespace std;#define uint unsigned int
#define lc(x) t[x].ch[0]
#define rc(x) t[x].ch[1]
#define fa(x) t[x].fa
const int MAXN = 1e5 + 5;
const int MOD = 51061;struct node{int ch[2], fa;uint val, sum, sz, add, mul;bool tag;node(){ch[1] = ch[0] = fa = 0;val = sum = sz = add = 0;mul = 1;tag = false;}
}t[MAXN];bool isroot(int x){return (lc(fa(x)) != x) && (rc(fa(x)) != x);
}void pushup(int x){t[x].sz = t[lc(x)].sz + t[rc(x)].sz + 1;t[x].sum = (t[lc(x)].sum + t[rc(x)].sum + t[x].val) % MOD;
}void update_rev(int x){if(!x) return;swap(lc(x), rc(x));t[x].tag ^= 1;
}void apply(int x, uint md, uint ad){if(!x) return;t[x].val = (1LL * t[x].val * md + ad) % MOD;t[x].sum = (1LL * t[x].sum * md + 1LL * ad * t[x].sz) % MOD;t[x].mul = (1LL * t[x].mul * md) % MOD;t[x].add = (1LL * t[x].add * md + ad) % MOD;
}void pushdown(int x){if(t[x].tag){update_rev(lc(x));update_rev(rc(x));t[x].tag = 0;}if(t[x].mul != 1 || t[x].add != 0){apply(lc(x), t[x].mul, t[x].add);apply(rc(x), t[x].mul, t[x].add);t[x].mul = 1, t[x].add = 0;}
}void rotate(int x){int y = fa(x), z = fa(y);int k = (rc(y) == x);if(!isroot(y)){t[z].ch[rc(z) == y] = x;}fa(x) = z;t[y].ch[k] = t[x].ch[k ^ 1];if(t[x].ch[k ^ 1]){fa(t[x].ch[k ^ 1]) = y;}t[x].ch[k ^ 1] = y;fa(y) = x;pushup(y);pushup(x);
}void pushshell(int x){if(!isroot(x)){pushshell(fa(x));}pushdown(x);
}void splay(int x){pushshell(x);while(!isroot(x)){int y = fa(x), z = fa(y);if(!isroot(y)){(rc(z) == y) ^ (rc(y) == x) ? rotate(x) : rotate(y);}rotate(x);}
}void access(int x){for(int y = 0;x;y = x, x = fa(x)){splay(x);rc(x) = y;pushup(x);}
}void makeroot(int x){access(x);splay(x);update_rev(x);
}int findrt(int x){access(x);splay(x);while(lc(x)){pushdown(x);x = lc(x);}splay(x);return x;
}void split(int x, int y){makeroot(x);access(y);splay(y);
}void link(int x, int y){makeroot(x);if(findrt(y) != x) fa(x) = y;
}void cut(int u1, int v1){split(u1, v1);if(lc(v1) == u1 && rc(u1) == 0){fa(u1) = lc(v1) = 0;pushup(v1);}
}int main(){int n, q;cin >> n >> q;for(int i = 1;i <= n;i ++){t[i].val = t[i].sum = t[i].sz = 1;t[i].mul = 1;}for(int i = 1;i < n;i ++){int u, v; cin >> u >> v;link(u, v);}while(q --){char op; cin >> op;int u, v, u2, v2; uint c;if(op == '+'){cin >> u >> v >> c;split(u, v);apply(v, 1, c);}else if(op == '-'){cin >> u >> v >> u2 >> v2;cut(u, v);link(u2, v2);}else if(op == '*'){cin >> u >> v >> c;split(u, v);apply(v, c, 0);}else if(op == '/'){cin >> u >> v;split(u, v);cout << t[v].sum << endl;}}return 0;
}