2020牛客多校第七场--C. A National Pandemic（树链剖分维护换根

题意：https://ac.nowcoder.com/acm/contest/5672/B

树上：3种操作，1。某点+x，2。某点清零，3。查询某点的值（计算方式是Sigma（val_to - dis(u,to))
思路：

考虑换根（我们肯定不能暴力换根），每次向下移动其实就是++--一些东西，在链上按点的贡献维护这种东西（树链剖分），查询也类型
  1 struct EDGE
  2 {
  3     int to,next;
  4 }edge[N<<1];
  5 int etot;
  6 int head[N];
  7 void Init(int n)
  8 {
  9     etot=0;
 10     for(int i=0;i<=n;++i)
 11         head[i]=0;
 12 }
 13 void add(int from,int to)
 14 {
 15     ++etot;
 16     edge[etot].to=to;
 17     edge[etot].next=head[from];
 18     head[from]=etot;
 19 }//for(int i=head[u];i;i=edge[i].next)
 20 
 21 
 22 
 23 int sum[N<<2];
 24 int lazy[N<<2];
 25 
 26 void up(int rt)
 27 {
 28     sum[rt]=sum[ls]+sum[rs];
 29 }
 30 
 31 void dn(int rt,int l,int r)
 32 {
 33     if(lazy[rt]!=0)
 34     {
 35         lazy[ls]+=lazy[rt];
 36         lazy[rs]+=lazy[rt];
 37         sum[ls]+=lazy[rt]*l;
 38         sum[rs]+=lazy[rt]*r;
 39         lazy[rt]=0;
 40     }
 41 }
 42 
 43 void Build(int l,int r,int rt)
 44 {
 45     sum[rt]=lazy[rt]=0;
 46     if(l==r)
 47     {
 48         return;
 49     }
 50     int mid=(l+r)>>1;
 51 
 52     Build(l,mid,rt<<1);
 53     Build(mid+1,r,rt<<1|1);
 54     up(rt);
 55 }
 56 void update_qu(int L,int R,int V,int l,int r,int rt)
 57 {
 58     if(L>R)return;
 59     if(L<=l&&r<=R)
 60     {
 61         sum[rt]+=V*(r-l+1);
 62         lazy[rt]+=V;
 63         return;
 64     }
 65 
 66     int mid=(l+r)>>1;
 67     dn(rt,mid-l+1,r-mid);
 68     if(L<=mid)
 69         update_qu(L,R,V,l,mid,rt<<1);
 70     if(R>mid)
 71         update_qu(L,R,V,mid+1,r,rt<<1|1);
 72     up(rt);
 73 }
 74 int Q(int L,int R,int l,int r,int rt)
 75 {
 76     if(L>R)return 0;
 77     if(L<=l&&r<=R)
 78     {
 79         return sum[rt];
 80     }
 81 
 82     int ans=0;
 83     int mid=(l+r)>>1;
 84     dn(rt,mid-l+1,r-mid);
 85     if(L<=mid)
 86         ans+=Q(L,R,l,mid,rt<<1);
 87     if(R>mid)
 88         ans+=Q(L,R,mid+1,r,rt<<1|1);
 89     up(rt);
 90     return ans;
 91 }
 92 
 93 
 94 class TREECUT//树链剖分
 95 {
 96 public:
 97     int DFN,n;
 98     int f[N],d[N],sz[N],hson[N],top[N],dfn[N],real[N];
 99     void Init(int _n)
100     {
101         DFN=0;
102         n=_n;
103         for(int i=0;i<=n;++i)
104             hson[i]=top[i]=real[i]=0;
105     }
106     void dfs1(int u,int fa,int deep)
107     {
108         sz[u]=1;
109         d[u]=deep;
110         f[u]=fa;
111         for(int i=head[u];i;i=edge[i].next)
112         {
113             int to=edge[i].to;
114             if(to==fa)continue;
115             dfs1(to,u,deep+1);
116             sz[u]+=sz[to];
117             if(sz[to]>sz[hson[u]])hson[u]=to;
118         }
119     }
120     void dfs2(int u,int t)
121     {
122         top[u]=t;
123         dfn[u]=++DFN;
124         real[DFN]=u;
125         if(!hson[u])return;
126         dfs2(hson[u],t);
127         for(int i=head[u];i;i=edge[i].next)
128         {
129             int to=edge[i].to;
130             if(to==f[u]||to==hson[u])continue;
131             dfs2(to,to);
132         }
133     }
134     void go_add(int x,int y)
135     {
136         int fx=top[x],fy=top[y];
137         while(fx!=fy)//两点不在同一条重链
138         {
139             if(d[fx]>=d[fy])
140             {
141                 update_qu(dfn[fx],dfn[x],2,1,n,1);
142 //                res.push_back({dfn[fx],dfn[x]});
143                 x=f[fx],fx=top[x];
144             }
145             else
146             {
147                 update_qu(dfn[fy],dfn[y],2,1,n,1);
148 //                res.push_back({dfn[fy],dfn[y]});
149                 y=f[fy],fy=top[y];
150             }
151         }
152         if(dfn[x]<=dfn[y])
153             update_qu(dfn[x],dfn[y],2,1,n,1);//,res.push_back({dfn[x],dfn[y]});//,LCA=x;
154         else
155             update_qu(dfn[y],dfn[x],2,1,n,1);//,res.push_back({dfn[y],dfn[x]});//,LCA=y;
156     }
157     int get_sum(int x,int y)
158     {
159         int ans=0,fx=top[x],fy=top[y];
160         while(fx!=fy)//两点不在同一条重链
161         {
162             if(d[fx]>=d[fy])
163             {
164                 ans+=Q(dfn[fx],dfn[x],1,n,1);
165                 x=f[fx],fx=top[x];
166             }
167             else
168             {
169                 ans+=Q(dfn[fy],dfn[y],1,n,1);
170                 y=f[fy],fy=top[y];
171             }
172         }
173         if(dfn[x]<=dfn[y])
174             ans+=Q(dfn[x],dfn[y],1,n,1);//,LCA=x;
175         else
176             ans+=Q(dfn[y],dfn[x],1,n,1);//,LCA=y;
177         return ans;
178     }
179 }TREE;
180 
181 int _0[N];
182 
183 void solve()
184 {
185     int n,m;
186     sc("%lld%lld",&n,&m);
187     for(int i=0;i<=n;++i)_0[i]=0;
188     Init(n);
189     TREE.Init(n);
190     for(int i=1;i<n;++i)
191     {
192         int u,v;
193         sc("%lld%lld",&u,&v);
194         add(u,v);
195         add(v,u);
196     }
197     Build(1,n,1);
198     TREE.dfs1(1,0,1);
199     TREE.dfs2(1,1);
200     int Vrt=0;
201     int add_ti=0;
202     for(int i=1;i<=m;++i)
203     {
204         int op,x,y;
205         sc("%lld",&op);
206         if(op==1)
207         {
208             sc("%lld%lld",&x,&y);
209             add_ti++;
210             TREE.go_add(1,x);
211             Vrt+=y-(TREE.d[x]-1);
212         }
213         else if(op==2)
214         {
215             sc("%lld",&x);
216             int val=Vrt-add_ti*(TREE.d[x]-1)+TREE.get_sum(1,x)-add_ti*2;
217             int real=val+_0[x];
218             if(real>0)_0[x]-=real;
219         }
220         else
221         {
222             sc("%lld",&x);
223 //            int temp=TREE.get_sum(1,x);
224 //            pr("%lld
",temp);
225             int val=Vrt-add_ti*(TREE.d[x]-1)+TREE.get_sum(1,x)-add_ti*2;
226             pr("%lld
",val+_0[x]);
227         }
228     }
229 }
230 
231 signed main()
232 {
233     int T;
234     sc("%lld",&T);
235     while(T--)solve();
236     return 0;
237 }