description
给定树，支持将树上与节点(x)距离不超过(d)的节点的点权均加上(w)，单点询问点权。
solution
动态点分治第四题。
同时第一次写线段树动态开点和标记永久化。。。
然后发现其实还挺简单的
code
#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<fstream>
#include<cstdlib>
#include<iomanip>
#include<cstring>
#include<complex>
#include<clocale>
#include<cctype>
#include<vector>
#include<cstdio>
#include<string>
#include<bitset>
#include<ctime>
#include<cmath>
#include<queue>
#include<stack>
#include<list>
#include<map>
#include<set>
#define FILE "a"
#define mp make_pair
#define pb push_back
#define RG register
#define il inline
//#define RAND
using namespace std;
typedef unsigned long long ull;
typedef vector<int>VI;
typedef long long ll;
typedef double dd;
const int inf=2147483647;
const dd pi=acos(-1);
const dd eps=1e-10;
const int mod=1e9+7;
const int N=100010;
const ll INF=1e18+1;
il ll read(){
RG ll data=0,w=1;RG char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')w=-1,ch=getchar();
while(ch<='9'&&ch>='0')data=data*10+ch-48,ch=getchar();
return data*w;
}
il int make(int l,int r){return rand()%(r-l+1)+l;}
il void file(){
#ifdef RAND
freopen("seed.in","r",stdin);
RG int seed=read();fclose(stdin);
srand(time(NULL)+seed);
freopen("seed.out","w",stdout);
seed=rand();printf("%d
",seed);
fclose(stdout);
freopen(FILE".in","w",stdout);
#endif
#ifndef RAND
freopen(FILE".in","r",stdin);
freopen(FILE".out","w",stdout);
#endif
}
/*********************************************************************/
int n,m;
int head[N],nxt[N<<1],to[N<<1],cnt;
il void add(int u,int v){
to[++cnt]=v;
nxt[cnt]=head[u];
head[u]=cnt;
}
int pa[N],siz[N],dep[N],son[N],top[N];
void dfs1(int u,int ff){
pa[u]=ff;siz[u]=1;dep[u]=dep[ff]+1;
for(RG int i=head[u];i;i=nxt[i]){
RG int v=to[i];if(v==ff)continue;
dfs1(v,u);siz[u]+=siz[v];
if(!son[u]||siz[son[u]]<siz[v])son[u]=v;
}
}
void dfs2(int u,int tp){
top[u]=tp;if(son[u])dfs2(son[u],tp);
for(RG int i=head[u];i;i=nxt[i]){
RG int v=to[i];if(v==pa[u]||v==son[u])continue;
dfs2(v,v);
}
}
il int lca(int u,int v){
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]])swap(u,v);
u=pa[top[u]];
}
return dep[u]<dep[v]?u:v;
}
il int dist(int u,int v){return dep[u]+dep[v]-2*dep[lca(u,v)];}
/*********************************************************************/
int RT,block,sz[N],w[N],fa[N],smd[N],tmd[N];bool vis[N];
void gettmd(int u,int ff,int nw,int d){
tmd[nw]=max(tmd[nw],d);
for(RG int i=head[u];i;i=nxt[i]){
RG int v=to[i];if(v==ff||vis[v])continue;
gettmd(v,u,nw,d+1);
}
}
void getsmd(int u,int ff,int nw,int d){
smd[nw]=max(smd[nw],d);
for(RG int i=head[u];i;i=nxt[i]){
RG int v=to[i];if(v==ff||vis[v])continue;
getsmd(v,u,nw,d+1);
}
}
void getrt(int u,int ff){
sz[u]=1;w[u]=0;
for(RG int i=head[u];i;i=nxt[i]){
RG int v=to[i];if(v==ff||vis[v])continue;
getrt(v,u);sz[u]+=sz[v];
w[u]=max(w[u],sz[v]);
}
w[u]=max(w[u],block-sz[u]);
if(w[RT]>w[u])RT=u;
}
void solve(int u,int ff){
fa[u]=ff;getsmd(u,0,u,0);vis[u]=1;
for(RG int i=head[u];i;i=nxt[i]){
RG int v=to[i];if(v==ff||vis[v])continue;
block=sz[v];RT=0;
getrt(v,0);
gettmd(v,0,RT,1);
solve(RT,u);
}
}
/*********************************************************************/
#define mid ((l+r)>>1)
int rt1[N],rt2[N],s[2][N<<5],sum[N<<5],tot;
il void modify(int &i,int l,int r,int x,int y,int w){
if(!i)i=++tot;
if(x<=l&&r<=y){sum[i]+=w;return;}
if(x<=mid)modify(s[0][i],l,mid,x,y,w);
if(mid<y)modify(s[1][i],mid+1,r,x,y,w);
}
il int query(int i,int l,int r,int p){
if(!i)return 0;if(l==r)return sum[i];RG int v=sum[i];
if(p<=mid)return v+query(s[0][i],l,mid,p);
else return v+query(s[1][i],mid+1,r,p);
}
/*********************************************************************/
il int Qry(int u){
RG int v=query(rt1[u],0,smd[u],0),d;
for(RG int x=u;fa[x];x=fa[x]){
d=dist(u,fa[x]);
v+=query(rt1[fa[x]],0,smd[fa[x]],d);
v-=query(rt2[x],0,tmd[x],d);
}
return v;
}
il void Mod(int u,int D,int w){
RG int d;modify(rt1[u],0,smd[u],0,min(smd[u],D),w);
for(RG int x=u;fa[x];x=fa[x]){
d=dist(u,fa[x]);if(D<d)continue;
modify(rt1[fa[x]],0,smd[fa[x]],0,min(smd[fa[x]],D-d),w);
modify(rt2[x],0,tmd[x],0,min(tmd[x],D-d),w);
}
}
/*********************************************************************/
int main()
{
n=read();m=read();block=w[0]=n;RT=0;
for(RG int i=1,u,v;i<n;i++){
u=read();v=read();add(u,v);add(v,u);
}
dfs1(1,0);dfs2(1,1);getrt(1,0);solve(RT,0);
for(RG int i=1,c,x,d,w;i<=m;i++){
c=0;while(c!='Q'&&c!='M')c=getchar();
if(c=='Q'){x=read();printf("%d
",Qry(x));}
else{x=read();d=read();w=read();Mod(x,d,w);}
}
return 0;
}