SHARE
TWEET

Untitled

a guest Mar 26th, 2020 80 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //#pragma comment(linker, "/STACK:1024000000,1024000000")
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
  5. const int MAXN = 1e5+7;
  6. const int MOD = 51061;
  7. struct LinkCutTree{
  8.     int_fast64_t val[MAXN],mul[MAXN],add[MAXN],sum[MAXN];
  9.     int tag[MAXN],sz[MAXN],fa[MAXN],ch[MAXN][2];
  10.     void pushup(int rt){
  11.         sz[rt] = sz[ch[rt][0]] + sz[ch[rt][1]] + 1;
  12.         sum[rt] = (sum[ch[rt][0]]+sum[ch[rt][1]]+val[rt])%MOD;
  13.     }
  14.     bool isroot(int rt){ return ch[fa[rt]][0]!=rt && ch[fa[rt]][1]!=rt; }
  15.     int check(int rt){ return rt == ch[fa[rt]][1]; }
  16.     void pushdownall(int rt){
  17.         if(!isroot(rt)) pushdownall(fa[rt]);
  18.         pushdown(rt);
  19.     }
  20.     void pushdown(int rt){
  21.         if(tag[rt]){
  22.             tag[rt] = 0;
  23.             tag[ch[rt][0]] ^= 1;
  24.             tag[ch[rt][1]] ^= 1;
  25.             swap(ch[rt][0],ch[rt][1]);
  26.         }
  27.         if(mul[rt]!=1){
  28.             if(ch[rt][0]){
  29.                 val[ch[rt][0]] = (val[ch[rt][0]]*mul[rt])%MOD;
  30.                 sum[ch[rt][0]] = (sum[ch[rt][0]]*mul[rt])%MOD;
  31.                 mul[ch[rt][0]] = (mul[ch[rt][0]]*mul[rt])%MOD;
  32.                 add[ch[rt][0]] = (add[ch[rt][0]]*mul[rt])%MOD;
  33.             }
  34.             if(ch[rt][1]){
  35.                 val[ch[rt][1]] = (val[ch[rt][1]]*mul[rt])%MOD;
  36.                 sum[ch[rt][1]] = (sum[ch[rt][1]]*mul[rt])%MOD;
  37.                 mul[ch[rt][1]] = (mul[ch[rt][1]]*mul[rt])%MOD;
  38.                 add[ch[rt][1]] = (add[ch[rt][1]]*mul[rt])%MOD;
  39.             }
  40.             mul[rt] = 1;
  41.         }
  42.         if(add[rt]){
  43.             if(ch[rt][0]){
  44.                 add[ch[rt][0]] = (add[ch[rt][0]]+add[rt])%MOD;
  45.                 sum[ch[rt][0]] = (sum[ch[rt][0]]+add[rt]*sz[ch[rt][0]])%MOD;
  46.                 val[ch[rt][0]] = (val[ch[rt][0]]+add[rt])%MOD;
  47.             }
  48.             if(ch[rt][1]){
  49.                 add[ch[rt][1]] = (add[ch[rt][1]]+add[rt])%MOD;
  50.                 sum[ch[rt][1]] = (sum[ch[rt][1]]+add[rt]*sz[ch[rt][1]])%MOD;
  51.                 val[ch[rt][1]] = (val[ch[rt][1]]+add[rt])%MOD;
  52.             }
  53.             add[rt] = 0;
  54.         }
  55.     }
  56.     void rorate(int rt){
  57.         int f = fa[rt], gf = fa[f], d = check(rt);
  58.         if(!isroot(f)) ch[gf][check(f)] = rt;
  59.         fa[rt] = gf;
  60.         ch[f][d] = ch[rt][d^1]; fa[ch[rt][d^1]] = f;
  61.         ch[rt][d^1] = f; fa[f] = rt;
  62.         pushup(f); pushup(rt);
  63.     }
  64.     void splay(int rt){
  65.         pushdownall(rt);
  66.         while(!isroot(rt)){
  67.             int f = fa[rt];
  68.             if(!isroot(f)){
  69.                 if(check(rt)==check(f)) rorate(f);
  70.                 else rorate(rt);
  71.             }
  72.             rorate(rt);
  73.         }
  74.     }
  75.     void access(int rt){
  76.         int c = 0;
  77.         while(rt){
  78.             splay(rt);
  79.             ch[rt][1] = c;
  80.             pushup(rt);
  81.             rt = fa[c=rt];
  82.         }
  83.     }
  84.     void makeroot(int rt){
  85.         access(rt);
  86.         splay(rt);
  87.         tag[rt]^=1;
  88.         pushdown(rt);
  89.     }
  90.     void split(int x, int y){
  91.         makeroot(x);
  92.         access(y);
  93.         splay(y);
  94.     }
  95.     void link(int x, int y){
  96.         makeroot(x);
  97.         fa[x] = y;
  98.     }
  99.     void cut(int x, int y){
  100.         split(x,y);
  101.         fa[x] = ch[y][0] = 0;
  102.         pushup(y);
  103.     }
  104.     void ADD(int u, int v, int c){
  105.         split(u,v);
  106.         add[v] = (add[v]+c)%MOD;
  107.         sum[v] = (sum[v]+c*sz[v])%MOD;
  108.         val[v] = (val[v]+c)%MOD;
  109.     }
  110.     void MUL(int u, int v, int c){
  111.         split(u,v);
  112.         add[v] = (add[v]*c)%MOD;
  113.         mul[v] = (mul[v]*c)%MOD;
  114.         sum[v] = (sum[v]*c)%MOD;
  115.         val[v] = (val[v]*c)%MOD;
  116.     }
  117.     int query(int u, int v){
  118.         split(u,v);
  119.         return sum[v];
  120.     }
  121. }LCT;
  122. int n,m;
  123. int main(){
  124.     scanf("%d %d",&n,&m);
  125.     for(int i = 1; i <= n; i++) LCT.val[i] = LCT.sum[i] = LCT.mul[i] = 1;
  126.     for(int i = 1; i < n; i++){
  127.         int u, v;
  128.         scanf("%d %d",&u,&v);
  129.         LCT.link(u,v);
  130.     }
  131.     while(m--){
  132.         char op[2];
  133.         scanf("%s",op);
  134.         if(op[0]=='+'){
  135.             int u, v, c;
  136.             scanf("%d %d %d",&u,&v,&c);
  137.             LCT.ADD(u,v,c);
  138.         }
  139.         else if(op[0]=='-'){
  140.             int u, v;
  141.             scanf("%d %d",&u,&v);
  142.             LCT.cut(u,v);
  143.             scanf("%d %d",&u,&v);
  144.             LCT.link(u,v);
  145.         }
  146.         else if(op[0]=='*'){
  147.             int u, v, c;
  148.             scanf("%d %d %d",&u,&v,&c);
  149.             LCT.MUL(u,v,c);
  150.         }
  151.         else if(op[0]=='/'){
  152.             int u, v;
  153.             scanf("%d %d",&u,&v);
  154.             printf("%d\n",LCT.query(u,v));
  155.         }
  156.     }
  157.     return 0;
  158. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top