Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //#pragma comment(linker, "/STACK:1024000000,1024000000")
- #include<bits/stdc++.h>
- using namespace std;
- function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
- const int MAXN = 1e5+7;
- const int MOD = 51061;
- struct LinkCutTree{
- int_fast64_t val[MAXN],mul[MAXN],add[MAXN],sum[MAXN];
- int tag[MAXN],sz[MAXN],fa[MAXN],ch[MAXN][2];
- void pushup(int rt){
- sz[rt] = sz[ch[rt][0]] + sz[ch[rt][1]] + 1;
- sum[rt] = (sum[ch[rt][0]]+sum[ch[rt][1]]+val[rt])%MOD;
- }
- bool isroot(int rt){ return ch[fa[rt]][0]!=rt && ch[fa[rt]][1]!=rt; }
- int check(int rt){ return rt == ch[fa[rt]][1]; }
- void pushdownall(int rt){
- if(!isroot(rt)) pushdownall(fa[rt]);
- pushdown(rt);
- }
- void pushdown(int rt){
- if(tag[rt]){
- tag[rt] = 0;
- tag[ch[rt][0]] ^= 1;
- tag[ch[rt][1]] ^= 1;
- swap(ch[rt][0],ch[rt][1]);
- }
- if(mul[rt]!=1){
- if(ch[rt][0]){
- val[ch[rt][0]] = (val[ch[rt][0]]*mul[rt])%MOD;
- sum[ch[rt][0]] = (sum[ch[rt][0]]*mul[rt])%MOD;
- mul[ch[rt][0]] = (mul[ch[rt][0]]*mul[rt])%MOD;
- add[ch[rt][0]] = (add[ch[rt][0]]*mul[rt])%MOD;
- }
- if(ch[rt][1]){
- val[ch[rt][1]] = (val[ch[rt][1]]*mul[rt])%MOD;
- sum[ch[rt][1]] = (sum[ch[rt][1]]*mul[rt])%MOD;
- mul[ch[rt][1]] = (mul[ch[rt][1]]*mul[rt])%MOD;
- add[ch[rt][1]] = (add[ch[rt][1]]*mul[rt])%MOD;
- }
- mul[rt] = 1;
- }
- if(add[rt]){
- if(ch[rt][0]){
- add[ch[rt][0]] = (add[ch[rt][0]]+add[rt])%MOD;
- sum[ch[rt][0]] = (sum[ch[rt][0]]+add[rt]*sz[ch[rt][0]])%MOD;
- val[ch[rt][0]] = (val[ch[rt][0]]+add[rt])%MOD;
- }
- if(ch[rt][1]){
- add[ch[rt][1]] = (add[ch[rt][1]]+add[rt])%MOD;
- sum[ch[rt][1]] = (sum[ch[rt][1]]+add[rt]*sz[ch[rt][1]])%MOD;
- val[ch[rt][1]] = (val[ch[rt][1]]+add[rt])%MOD;
- }
- add[rt] = 0;
- }
- }
- void rorate(int rt){
- int f = fa[rt], gf = fa[f], d = check(rt);
- if(!isroot(f)) ch[gf][check(f)] = rt;
- fa[rt] = gf;
- ch[f][d] = ch[rt][d^1]; fa[ch[rt][d^1]] = f;
- ch[rt][d^1] = f; fa[f] = rt;
- pushup(f); pushup(rt);
- }
- void splay(int rt){
- pushdownall(rt);
- while(!isroot(rt)){
- int f = fa[rt];
- if(!isroot(f)){
- if(check(rt)==check(f)) rorate(f);
- else rorate(rt);
- }
- rorate(rt);
- }
- }
- void access(int rt){
- int c = 0;
- while(rt){
- splay(rt);
- ch[rt][1] = c;
- pushup(rt);
- rt = fa[c=rt];
- }
- }
- void makeroot(int rt){
- access(rt);
- splay(rt);
- tag[rt]^=1;
- pushdown(rt);
- }
- void split(int x, int y){
- makeroot(x);
- access(y);
- splay(y);
- }
- void link(int x, int y){
- makeroot(x);
- fa[x] = y;
- }
- void cut(int x, int y){
- split(x,y);
- fa[x] = ch[y][0] = 0;
- pushup(y);
- }
- void ADD(int u, int v, int c){
- split(u,v);
- add[v] = (add[v]+c)%MOD;
- sum[v] = (sum[v]+c*sz[v])%MOD;
- val[v] = (val[v]+c)%MOD;
- }
- void MUL(int u, int v, int c){
- split(u,v);
- add[v] = (add[v]*c)%MOD;
- mul[v] = (mul[v]*c)%MOD;
- sum[v] = (sum[v]*c)%MOD;
- val[v] = (val[v]*c)%MOD;
- }
- int query(int u, int v){
- split(u,v);
- return sum[v];
- }
- }LCT;
- int n,m;
- int main(){
- scanf("%d %d",&n,&m);
- for(int i = 1; i <= n; i++) LCT.val[i] = LCT.sum[i] = LCT.mul[i] = 1;
- for(int i = 1; i < n; i++){
- int u, v;
- scanf("%d %d",&u,&v);
- LCT.link(u,v);
- }
- while(m--){
- char op[2];
- scanf("%s",op);
- if(op[0]=='+'){
- int u, v, c;
- scanf("%d %d %d",&u,&v,&c);
- LCT.ADD(u,v,c);
- }
- else if(op[0]=='-'){
- int u, v;
- scanf("%d %d",&u,&v);
- LCT.cut(u,v);
- scanf("%d %d",&u,&v);
- LCT.link(u,v);
- }
- else if(op[0]=='*'){
- int u, v, c;
- scanf("%d %d %d",&u,&v,&c);
- LCT.MUL(u,v,c);
- }
- else if(op[0]=='/'){
- int u, v;
- scanf("%d %d",&u,&v);
- printf("%d\n",LCT.query(u,v));
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement