题目
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
Sample Output
2
3
6
HINT
数据范围：
n，m<=10^5,-10^4<=w<=10^4
注意：w不一定为正整数，因为烁烁可能把皮皮鼠吓傻了。
题解
跟[BZOJ3730]震波差不多……
线段树里还是存距离为下标的权值和，这里需要区间修改、单点查询，所以你甚至可以不用维护区间和
因为空间开小WA了一发……忘记去文件操作TLE了一发……老年痴呆没跑了
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
# define X first
# define Y second
# define tl s[k].l
# define tr s[k].r
# define _tl s[_k].l
# define _tr s[_k].r
# define mid (l+r>>1)
# define mp make_pair
# define Pi pair<int,int>
using namespace std;
const int MAX=1e5+5;
struct p{
int x,y;
}c[MAX<<1];
struct q{
int _x,x,l,r;
}s[MAX<<7];
int n,m,num,Sum,rt,tot;
int h[MAX],Rt[MAX],d[MAX],top[MAX],fa[MAX],siz[MAX],son[MAX],f[MAX],F[MAX];
bool use[MAX];
int read()
{
int x=0,fl=1;
char ch=getchar();
for(;!isdigit(ch);fl=(ch=='-')?-1:1,ch=getchar());
for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
return x*fl;
}
int max(int x,int y) {return x>y?x:y;}
void add(int x,int y)
{
c[++num]=(p){h[x],y},h[x]=num;
c[++num]=(p){h[y],x},h[y]=num;
}
void GET_ROOT(int x=1,int fa=0)
{
f[x]=0,siz[x]=1;
for(int i=h[x];i;i=c[i].x)
if((c[i].y^fa)&&!use[c[i].y]) GET_ROOT(c[i].y,x),f[x]=max(f[x],siz[c[i].y]),siz[x]+=siz[c[i].y];
f[x]=max(f[x],Sum-siz[x]);
if(f[x]<f[rt]) rt=x;
}
void dfs(int x=rt)
{
use[x]=1;
int xsum=Sum;
for(int i=h[x];i;i=c[i].x)
if(!use[c[i].y])
{
if(siz[c[i].y]>siz[x]) Sum=xsum-siz[x];
else Sum=siz[c[i].y];
f[rt=0]=Sum,GET_ROOT(c[i].y,x),F[rt]=x,dfs(rt);
}
}
void dfs_(int x=1,int F=0)
{
fa[x]=F,d[x]=d[F]+(siz[x]=1);
for(int i=h[x];i;i=c[i].x)
if(c[i].y^F)
{
dfs_(c[i].y,x),siz[x]+=siz[c[i].y];
if(siz[c[i].y]>siz[son[x]]) son[x]=c[i].y;
}
}
void dfs__(int x=1,int tp=1)
{
top[x]=tp;
if(!son[x]) return;
dfs__(son[x],tp);
for(int i=h[x];i;i=c[i].x)
if((c[i].y^fa[x])&&(c[i].y^son[x])) dfs__(c[i].y,c[i].y);
}
int LCA(int x,int y)
{
while(top[x]^top[y])
{
if(d[top[x]]<d[top[y]]) swap(x,y);
x=fa[top[x]];
}
return d[x]>d[y]?y:x;
}
int GET_DIS(int x,int y) {return d[x]+d[y]-(d[LCA(x,y)]<<1);}
void down(int k,int _k=0)
{
int F;
if(s[k].x)
{
if(!tl) tl=++tot;
if(!tr) tr=++tot;
F=s[k].x,s[k].x=0,s[tl].x+=F,s[tr].x+=F;
}
if(s[_k].x)
{
if(!_tl) _tl=++tot;
if(!_tr) _tr=++tot;
F=s[_k].x,s[_k].x=0,s[_tl].x+=F,s[_tr].x+=F;
}
if(s[k]._x)
{
if(!tl) tl=++tot;
if(!tr) tr=++tot;
F=s[k]._x,s[k]._x=0,s[tl]._x+=F,s[tr]._x+=F;
}
if(s[_k]._x)
{
if(!_tl) _tl=++tot;
if(!_tr) _tr=++tot;
F=s[_k]._x,s[_k]._x=0,s[_tl]._x+=F,s[_tr]._x+=F;
}
}
void change(int l,int r,int &k,int &_k,int L,int R,int dis)
{
if(r<L||R<l) return;
if(!k) k=++tot;
if(!_k) _k=++tot;
if(l>=L&&r<=R)
{
s[k].x+=dis;
return void(s[_k]._x+=dis);
}
down(k,_k),change(l,mid,tl,_tl,L,R,dis),change(mid+1,r,tr,_tr,L,R,dis);
}
void change(int l,int r,int &k,int L,int R,int dis)
{
if(r<L||R<l) return;
if(!k) k=++tot;
if(l>=L&&r<=R) return void(s[k].x+=dis);
down(k),change(l,mid,tl,L,R,dis),change(mid+1,r,tr,L,R,dis);
}
Pi ask(int l,int r,int k,int _k,int x)
{
if(!k&&!_k) return mp(0,0);
if(l==r) return mp(s[k].x,s[_k]._x);
down(k,_k);
if(x<=mid) return ask(l,mid,tl,_tl,x);
return ask(mid+1,r,tr,_tr,x);
}
void change(int x,int d,int w)
{
change(1,n,Rt[x],1,d+1,w);
for(int i=x,_d;F[i];i=F[i])
{
_d=GET_DIS(F[i],x);
if(_d<=d) change(1,n,Rt[F[i]],Rt[i],1,d-_d+1,w);
}
}
int ask(int x)
{
Pi A;
int ans=ask(1,n,Rt[x],0,1).X;
for(int i=x,_d;F[i];i=F[i])
_d=GET_DIS(F[i],x),A=ask(1,n,Rt[F[i]],Rt[i],_d+1),ans+=A.X-A.Y;
return ans;
}
int main()
{
n=read(),m=read();
for(int i=1,x;i<n;++i)
x=read(),add(x,read());
dfs_(),dfs__(),Sum=f[rt]=n,GET_ROOT(),dfs();
for(int i=1,x,d;i<=m;++i)
{
char ch=getchar();
for(;ch!='Q'&&ch!='M';ch=getchar());
if(ch=='Q') printf("%d\n",ask(read()));
else if(ch=='M') x=read(),d=read(),change(x,d,read());
}
return 0;
}
