“震波”题意
3730: 震波
Time Limit: 15 Sec Memory Limit: 256 MB
Submit: 4891 Solved: 869
[Submit][Status][Discuss]
Description
在一片土地上有N个城市，通过N-1条无向边互相连接，形成一棵树的结构，相邻两个城市的距离为1，其中第i个城市的价值为value[i]。
不幸的是，这片土地常常发生地震，并且随着时代的发展，城市的价值也往往会发生变动。
接下来你需要在线处理M次操作：
0 x k 表示发生了一次地震，震中城市为x，影响范围为k，所有与x距离不超过k的城市都将受到影响，该次地震造成的经济损失为所有受影响城市的价值和。
1 x y 表示第x个城市的价值变成了y。
为了体现程序的在线性，操作中的x、y、k都需要异或你程序上一次的输出来解密，如果之前没有输出，则默认上一次的输出为0。
Input
第一行包含两个正整数N和M。
第二行包含N个正整数，第i个数表示value[i]。
接下来N-1行，每行包含两个正整数u、v，表示u和v之间有一条无向边。
接下来M行，每行包含三个数，表示M次操作。
Output
包含若干行，对于每个询问输出一行一个正整数表示答案。
Sample Input
8 1
1 10 100 1000 10000 100000 1000000 10000000
1 2
1 3
2 4
2 5
3 6
3 7
3 8
0 3 1
Sample Output
11100101
HINT
1<=N,M<=100000
1<=u,v,x<=N
1<=value[i],y<=10000
0<=k<=N-1
Source
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,|w|<=10^4
注意：w不一定为正整数，因为烁烁可能把皮皮鼠吓傻了。
Source
分析
这两个题的关系，类似树状数组单点加区间查询和区间加单点查询的关系。
建出点分树后，建立以距离为下标，修改的差分标记为内容的树状数组。这样修改操作就用在点分树上跳，用两个树状数组容斥地维护差分标记。查询的时候也在点分树上跳，沿途求出对应距离的差分值，加起来就是答案了。
打得我有点头晕。树状数组只维护距离节点距离>1的点的标记，另开一个`val`维护自己。
co int N=1e5+1;
int n,m,siz[N],f[N],root,sum,vis[N];
vector<int> e[N];
void get_root(int u,int fa){
siz[u]=1,f[u]=0;
for(int i=0,v;i<e[u].size();++i){
if(vis[v=e[u][i]]||v==fa) continue;
get_root(v,u);
siz[u]+=siz[v],f[u]=max(f[u],siz[v]);
}
f[u]=max(f[u],sum-siz[u]);
if(f[u]<f[root]) root=u;
}
int dep[N],fa[N][20],dis[N][20];
void get_shipped(int u,int fa,int anc,int d){
for(int i=0,v;i<e[u].size();++i){
if(vis[v=e[u][i]]||v==fa) continue;
::fa[v][++dep[v]]=anc,dis[v][dep[v]]=d,get_shipped(v,u,anc,d+1);
}
}
int val[N];
vector<int> bit[N],fbit[N];
void build_tree(int u){
vis[u]=1,get_shipped(u,0,u,1);
int all=sum;bit[u].resize(all+1),fbit[u].resize(all+1);
for(int i=0,v;i<e[u].size();++i){
if(vis[v=e[u][i]]) continue;
sum=siz[v];if(sum>siz[u]) sum=all-siz[u];
root=0,get_root(v,u),build_tree(root);
}
}
#define lowbit(i) (i&-i)
int query(int x){
int re=val[x];
for(int i=dep[x];i;--i){
for(int j=dis[x][i];j;j-=lowbit(j)) re+=bit[fa[x][i]][j];
for(int j=min(dis[x][i],(int)fbit[fa[x][i+1]].size()-1);j;j-=lowbit(j)) re-=fbit[fa[x][i+1]][j];
}
return re;
}
void add(int x,int d,int w){
for(int i=d;i<bit[x].size();i+=lowbit(i)) bit[x][i]+=w;
}
void addf(int x,int d,int w){
for(int i=d;i<fbit[x].size();i+=lowbit(i)) fbit[x][i]+=w;
}
void change(int x,int d,int w){
val[x]+=w;
int lim=min((int)bit[x].size()-1,d);
add(x,1,w),add(x,d+1,-w);
for(int i=dep[x];i;--i)if(dis[x][i]<=d){
val[fa[x][i]]+=w,add(fa[x][i],1,w),add(fa[x][i],d-dis[x][i]+1,-w);
addf(fa[x][i+1],1,w),addf(fa[x][i+1],d-dis[x][i]+1,-w);
}
}
int main(){
read(n),read(m);
for(int i=1,u,v;i<n;++i){
read(u),read(v);
e[u].push_back(v),e[v].push_back(u);
}
f[0]=n,sum=n,get_root(1,0),build_tree(root);
for(int i=1;i<=n;++i) fa[i][dep[i]+1]=i;
for(int x,d,w;m--;){
static char op[2];scanf("%s",op);
if(op[0]=='Q') read(x),printf("%d\n",query(x));
else read(x),read(d),read(w),change(x,d,w);
}
return 0;
}
