建立点分树，每个分治中心开一个树状数组，表示它对所有到它距离为ttt的点的贡献
每次修改直接暴跳分治树父亲修改，发现父子分治中心会对一些点有重复贡献，每个儿子开一个树状表示它的连通块内距离父亲不超过ttt的点被重复贡献了多少。
询问暴跳点分树查每一个分治中心的树状数组即可。
代码：
#include<bits/stdc++.h>#definelllonglong#definereregister#definecsconstnamespaceIO{staticcsintRlen=1<<22|1;staticcharbuf[Rlen],*p1,*p2;inlinechargc(){return(p1==p2)&&(p2=(p1=buf)+fread(buf,1,Rlen,stdin),p1==p2)?EOF:*p1++;}inlinecharpeek(){return(p1==p2)&&(p2=(p1=buf)+fread(buf,1,Rlen,stdin),p1==p2)?EOF:*p1;}inlinecharga(){while(!isalpha(peek()))++p1;return*p1++;}template<typenameT>inlineTget(){charc;Tnum;boolf=0;while(!isdigit(c=gc()))f=c=='-';num=c^48;while(isdigit(c=gc()))num=(num+(num<<2)<<1)+(c^48);returnf?-num:num;}inlineintgi(){returnget<int>();}}usingnamespaceIO;usingstd::cerr;usingstd::cout;csintN=1e5+7;intn,m;std::vector<int>G[N];inlinevoidadde(intu,intv){G[u].push_back(v);G[v].push_back(u);}namespaceST{intin[N],dfn,d[N],mn[19][N<<1],Log[N<<1];voiddfs(intu,intp){mn[0][in[u]=++dfn]=d[u]=d[p]+1;for(intrev:G[u])if(v!=p)dfs(v,u),mn[0][++dfn]=d[u];}inlinevoidinit(){dfs(1,0);for(intrei=2;i<=dfn;++i)Log[i]=Log[i>>1]+1;for(intrei=1;i<=Log[dfn];++i)for(intrej=1;j+(1<<i)-1<=dfn;++j)mn[i][j]=std::min(mn[i-1][j],mn[i-1][j+(1<<i-1)]);}inlineintdis(intu,intv){intl=in[u],r=in[v];if(l>r)std::swap(l,r);intt=Log[r-l+1];returnd[u]+d[v]-2*std::min(mn[t][l],mn[t][r-(1<<t)+1]);}}usingST::dis;intfa[N],ban[N],siz[N];intrt,total,mx_siz;voidget_siz(intu,intp){siz[u]=1;for(intrev:G[u])if(v!=p&&!ban[v]){get_siz(v,u);siz[u]+=siz[v];}}voidfind_rt(intu,intp){intmx=total-siz[u];for(intrev:G[u])if(v!=p&&!ban[v]){find_rt(v,u);mx=std::max(mx,siz[v]);}if(mx<mx_siz){mx_siz=mx,rt=u;}}voidget_rt(intu){get_siz(u,0);total=siz[u],mx_siz=0x3f3f3f3f;find_rt(u,0);}structBIT{std::vector<int>a;intn;inlinevoidinit(int_n){n=_n+1;a.resize(n+1);}inlinevoidadd(intp,intv){for(p=std::min(p+1,n);p>=1;p^=p&-p)a[p]+=v;}inlineintquery(intp){intres=0;for(p=std::min(p+1,n);p<=n;p+=p&-p)res+=a[p];returnres;}}f1[N],f2[N];intmxd;voidget_d(intu,intp,intd){mxd=std::max(d,mxd);for(intrev:G[u])if(v!=p&&!ban[v])get_d(v,u,d+1);}voidDFS(intu){ban[u]=true;mxd=0;get_d(u,0,0);f1[u].init(mxd);for(intrev:G[u])if(!ban[v]){get_rt(v);fa[rt]=u;mxd=0;get_d(v,0,1);f2[rt].init(mxd);DFS(rt);}}inlineintquery(intu){intans=0;for(intrev=u;v;v=fa[v]){ans+=f1[v].query(dis(u,v));if(fa[v])ans-=f2[v].query(dis(u,fa[v]));}returnans;}inlinevoidmodify(intu,intd,intw){for(intrev=u;v;v=fa[v]){f1[v].add(d-dis(u,v),w);if(fa[v])f2[v].add(d-dis(u,fa[v]),w);}}signedmain(){#ifdefzxyoifreopen("game.in","r",stdin);#endifn=gi(),m=gi();for(intrei=1;i<n;++i)adde(gi(),gi());ST::init();get_rt(1);DFS(rt);while(m--){switch(ga()){case'Q':cout<<query(gi())<<"\n";break;case'M':{intu=gi(),d=gi(),w=gi();modify(u,d,w);break;}}}return0;}
