题目传送门
前置知识
动态树分治 | 动态开点线段树 | 标记永久化
解法
考虑动态点分治。
两种操作本质上是将 luogu P6329 【模板】点分树 | 震波 的操作互换了下，将原需支持单点修改、区间查询的数据结构换成需支持区间修改、单点查询的数据结构即可。
区间修改、单点查询的动态开点线段树可以考虑标记永久化。
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define sort stable_sort
#define endl '\n'
struct node
{int nxt,to;
}e[200010];
int head[200010],ask,cnt=0;
void add(int u,int v)
{cnt++;e[cnt].nxt=head[u];e[cnt].to=v;head[u]=cnt;
}
struct LCA
{int siz[200010],fa[200010],dep[200010],son[200010],top[200010];void init(){dfs1(1,0);dfs2(1,1);}void dfs1(int x,int father){siz[x]=1;fa[x]=father;dep[x]=dep[father]+1;for(int i=head[x];i!=0;i=e[i].nxt){if(e[i].to!=father){dfs1(e[i].to,x);siz[x]+=siz[e[i].to];son[x]=(siz[e[i].to]>siz[son[x]])?e[i].to:son[x];}}}void dfs2(int x,int id){top[x]=id;if(son[x]!=0){dfs2(son[x],id);for(int i=head[x];i!=0;i=e[i].nxt){if(e[i].to!=son[x]&&e[i].to!=fa[x]){dfs2(e[i].to,e[i].to);}}}}int lca(int u,int v){while(top[u]!=top[v]){if(dep[top[u]]>dep[top[v]]){u=fa[top[u]];}else{v=fa[top[v]];}}return (dep[u]<dep[v])?u:v;}int get_dis(int x,int y){return dep[x]+dep[y]-2*dep[lca(x,y)];}
}L;
struct SMT
{int root[200010],rt_sum=0;struct SegmentTree{int ls,rs,lazy;}tree[200010<<5];#define lson(rt) (tree[rt].ls)#define rson(rt) (tree[rt].rs)int build_rt(){rt_sum++;lson(rt_sum)=rson(rt_sum)=tree[rt_sum].lazy=0;return rt_sum;}void update(int &rt,int l,int r,int x,int y,int val){ if(rt==0){rt=build_rt();}if(x<=l&&r<=y){ tree[rt].lazy+=val;return;}int mid=(l+r)/2;if(x<=mid){update(lson(rt),l,mid,x,y,val);}if(y>mid){update(rson(rt),mid+1,r,x,y,val);}}int query(int rt,int l,int r,int pos){if(rt==0){return 0;}if(l==r){return tree[rt].lazy;}int mid=(l+r)/2;if(pos<=mid){return query(lson(rt),l,mid,pos)+tree[rt].lazy;}else{return query(rson(rt),mid+1,r,pos)+tree[rt].lazy;}}
}T[2];
struct Divide_On_Tree
{int siz[200010],weight[200010],vis[200010],fa[200010],center=0;void init(int n){center=0;get_center(1,0,n);get_siz(center,0);build(center);}void get_center(int x,int fa,int n){siz[x]=1;weight[x]=0;for(int i=head[x];i!=0;i=e[i].nxt){if(e[i].to!=fa&&vis[e[i].to]==0){get_center(e[i].to,x,n);siz[x]+=siz[e[i].to];weight[x]=max(weight[x],siz[e[i].to]);}}weight[x]=max(weight[x],n-siz[x]);if(weight[x]<=n/2){center=x;}}void get_siz(int x,int fa){siz[x]=1;for(int i=head[x];i!=0;i=e[i].nxt){if(e[i].to!=fa&&vis[e[i].to]==0){get_siz(e[i].to,x);siz[x]+=siz[e[i].to];}}}void build(int x){vis[x]=1;for(int i=head[x];i!=0;i=e[i].nxt){if(vis[e[i].to]==0){center=0;get_center(e[i].to,0,siz[e[i].to]);get_siz(center,0);fa[center]=x;build(center);}}}void update(int x,int k,int val){T[0].update(T[0].root[x],0,ask,0,k,val);for(int rt=x;fa[rt]!=0;rt=fa[rt]){if(L.get_dis(fa[rt],x)<=k){T[0].update(T[0].root[fa[rt]],0,ask,0,k-L.get_dis(fa[rt],x),val);T[1].update(T[1].root[rt],0,ask,0,k-L.get_dis(fa[rt],x),val);}}}int query(int x){int ans=T[0].query(T[0].root[x],0,ask,0);for(int rt=x;fa[rt]!=0;rt=fa[rt]){ans+=T[0].query(T[0].root[fa[rt]],0,ask,L.get_dis(fa[rt],x));ans-=T[1].query(T[1].root[rt],0,ask,L.get_dis(fa[rt],x));}return ans;}
}D;
int main()
{int n,m,u,v,x,d,w,i;char pd;cin>>n>>m;ask=n;for(i=1;i<=n-1;i++){cin>>u>>v;add(u,v);add(v,u);}L.init();D.init(n);for(i=1;i<=m;i++){cin>>pd;if(pd=='Q'){cin>>x;cout<<D.query(x)<<endl;}else{cin>>x>>d>>w; D.update(x,d,w);}}return 0;
}
