Description
背景：烁烁很喜欢爬树，这吓坏了树上的皮皮鼠。
题意：
给定一颗n个节点的树，边权均为1，初始树上没有皮皮鼠。
烁烁他每次会跳到一个节点u，把周围与他距离不超过d的节点各吸引出w只皮皮鼠。皮皮鼠会被烁烁吸引，所以会一直待在节点上不动。
烁烁很好奇，在当前时刻，节点u有多少个他的好朋友---皮皮鼠。
大意：
给一颗n个节点的树，边权均为1，初始点权均为0，m次操作：
Q x：询问x的点权。
M x d w：将树上与节点x距离不超过d的节点的点权均加上w。
Input
第一行两个正整数：n，m
接下来的n-1行，每行三个正整数u，v，代表u，v之间有一条边。
接下来的m行，每行给出上述两种操作中的一种。
Output
对于每个Q操作，输出当前x节点的皮皮鼠数量。
Sample Input
7 6
1 2
1 4
1 5
2 3
2 7
5 6
M 1 1 2
Q 5
M 2 2 3
Q 3
M 1 2 1
Q 2
1 2
1 4
1 5
2 3
2 7
5 6
M 1 1 2
Q 5
M 2 2 3
Q 3
M 1 2 1
Q 2
Sample Output
2
3
6
3
6
解题思路：
和震波很像，查询修改反过来就好了。
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
const int N=;
struct pnt{
int hd;
int fa;
int f;
int tp;
int wgt;
int mxs;
int dis;
bool vis;
int roota;
int rootp;
}p[N];
struct trnt{
int ls;
int rs;
int val;
}tr[];
struct ent{
int twd;
int lst;
}e[N<<];
int n,m;
int cnt;
int siz;
int root;
int size;
int maxsize;
char cmd[];
void ade(int f,int t)
{
cnt++;
e[cnt].twd=t;
e[cnt].lst=p[f].hd;
p[f].hd=cnt;
return ;
}
void Basic_dfs(int x,int f)
{
p[x].dis=p[f].dis+;
p[x].f=f;
p[x].wgt=;
int maxs=-;
for(int i=p[x].hd;i;i=e[i].lst)
{
int to=e[i].twd;
if(to==f)
continue;
Basic_dfs(to,x);
p[x].wgt+=p[to].wgt;
if(maxs<p[to].wgt)
{
maxs=p[to].wgt;
p[x].mxs=to;
}
}
return ;
}
void Build_dfs(int x,int top)
{
if(!x)
return ;
p[x].tp=top;
Build_dfs(p[x].mxs,top);
for(int i=p[x].hd;i;i=e[i].lst)
{
int to=e[i].twd;
if(to==p[x].mxs||to==p[x].f)
continue;
Build_dfs(to,to);
}
return ;
}
int Lca(int x,int y)
{
while(p[x].tp!=p[y].tp)
{
if(p[p[x].tp].dis<p[p[y].tp].dis)
std::swap(x,y);
x=p[p[x].tp].f;
}
if(p[x].dis>p[y].dis)
std::swap(x,y);
return x;
}
int Dis(int x,int y)
{
int z=Lca(x,y);
return p[x].dis+p[y].dis-*p[z].dis;
}
void grc_dfs(int x,int f)
{
p[x].wgt=;
int maxs=-;
for(int i=p[x].hd;i;i=e[i].lst)
{
int to=e[i].twd;
if(to==f||p[to].vis)
continue;
grc_dfs(to,x);
p[x].wgt+=p[to].wgt;
if(maxs<p[to].wgt)
maxs=p[to].wgt;
}
maxs=std::max(maxs,size-p[x].wgt);
if(maxs<maxsize)
{
root=x;
maxsize=maxs;
}
return ;
}
void bin_dfs(int x,int f)
{
p[x].fa=f;
p[x].vis=true;
int tmp=size;
for(int i=p[x].hd;i;i=e[i].lst)
{
int to=e[i].twd;
if(p[to].vis)
continue;
root=;
if(p[x].wgt>p[to].wgt)
size=p[to].wgt;
else
size=tmp-p[x].wgt;
maxsize=0x3f3f3f3f;
grc_dfs(to,to);
bin_dfs(root,x);
}
return ;
}
void update(int &spc,int l,int r,int ll,int rr,int v)
{
if(ll>r||l>rr)
return ;
if(!spc)
spc=++siz;
if(ll<=l&&r<=rr)
{
tr[spc].val+=v;
return ;
}
int mid=(l+r)>>;
update(tr[spc].ls,l,mid,ll,rr,v);
update(tr[spc].rs,mid+,r,ll,rr,v);
return ;
}
int query(int spc,int l,int r,int pos)
{
if(!spc)
return ;
int ans=tr[spc].val;
if(l==r)
return ans;
int mid=(l+r)>>;
if(pos<=mid)
ans+=query(tr[spc].ls,l,mid,pos);
else
ans+=query(tr[spc].rs,mid+,r,pos);
return ans;
}
void Update(int x,int k,int val)
{
update(p[x].rootp,,n-,,k,val);
for(int i=x;p[i].fa;i=p[i].fa)
{
int d=Dis(x,p[i].fa);
if(k<d)
continue;
update(p[p[i].fa].rootp,,n-,,k-d,val);
update(p[i].roota,,n-,,k-d,val);
}
return ;
}
int Query(int x)
{
int ans=query(p[x].rootp,,n-,);
for(int i=x;p[i].fa;i=p[i].fa)
{
int d=Dis(x,p[i].fa);
ans+=query(p[p[i].fa].rootp,,n-,d)-query(p[i].roota,,n-,d);
}
return ans;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<n;i++)
{
int a,b;
scanf("%d%d",&a,&b);
ade(a,b);
ade(b,a);
}
Basic_dfs(,);
Build_dfs(,);
root=;
size=n;
maxsize=0x3f3f3f3f;
grc_dfs(,);
bin_dfs(root,);
while(m--)
{
scanf("%s",cmd+);
if(cmd[]=='M')
{
int x,k,v;
scanf("%d%d%d",&x,&k,&v);
Update(x,k,v);
}else{
int x;
scanf("%d",&x);
printf("%d\n",Query(x));
}
}
return ;
}