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
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
点分，每个重心按距离建一颗线段树记录该块内的城市价值。
另外多建一颗去重线段树，表示该块内从重心的某个儿子的子树内的城市价值。（去重线段树合并起来就是原线段树）
每个节点都连一条新边到深度更浅的重心。
修改时遍历一发连的新边，在更浅的重心的线段树及去重线段树处暴力修改。
查询时同样遍历所有新边，然后累计和去重。
码了好久……
#include<cstdio> #include<algorithm> #define MN 200001 using namespace std; int read_p,read_ca; inline int read(){ read_p=0;read_ca=getchar(); while(read_ca<'0'||read_ca>'9') read_ca=getchar(); while(read_ca>='0'&&read_ca<='9') read_p=read_p*10+read_ca-48,read_ca=getchar(); return read_p; } struct na{ int x,y,z,ne; }b[200001],bb[6000001]; struct tree{ int l,r,k; }t[10000001]; int n,m,ma,la[MN],num=0,fa[MN],s[MN],size,root,va[MN],nm=0,ro[MN],lo[MN],op[MN],rot[MN],uu,nnmm=0,lla[MN],nnum=0; bool v[MN]; const int INF=1e9; inline void in(int x,int y){b[++num].y=y;b[num].ne=la[x];la[x]=num;} inline void in(int u,int x,int y,int z){bb[++nnum].x=x;bb[nnum].y=y;bb[nnum].z=z;bb[nnum].ne=lla[u];lla[u]=nnum;} inline void in(int &p,int l,int r,int x,int k){if (!p) p=++nm;t[p].k+=k;if (l==r) return;int mid=l+r>>1;if (x<=mid) in(t[p].l,l,mid,x,k);else in(t[p].r,mid+1,r,x,k);} inline int que(int p,int l,int r,int x){if (!p||x<l) return 0;if (x==r) return t[p].k;int mid=l+r>>1;if (x<=mid) return que(t[p].l,l,mid,x);else return que(t[p].l,l,mid,mid)+que(t[p].r,mid+1,r,x);} inline void gs(int x,int f){ int u=0;s[x]=1; for (int i=la[x];i;i=b[i].ne) if (!v[b[i].y]&&b[i].y!=f) gs(b[i].y,x),s[x]+=s[b[i].y],u=u>s[b[i].y]?u:s[b[i].y]; if (u<size-s[x]) u=size-s[x]; if (u<ma) root=x,ma=u; } inline void dfs(int x,int f,int dis){ if (dis==1) uu=++nnmm; if (f) in(ro[root],1,n,dis,va[x]),in(rot[uu],1,n,dis,va[x]),in(x,root,uu,dis); for (int i=la[x];i;i=b[i].ne) if (b[i].y!=f&&(!v[b[i].y])) dfs(b[i].y,x,dis+1); } inline void work(int x,int siz,int f){ size=siz;ma=INF;gs(x,0);dfs(root,0,0);x=root;v[root]=1; for (int i=la[x];i;i=b[i].ne) if (!v[b[i].y]) work(b[i].y,s[b[i].y],x); } inline int qu(int x,int k){ int ans=que(ro[x],1,n,k)+va[x]; for (register int j=lla[x];j;j=bb[j].ne){if (k>=bb[j].z) ans+=va[bb[j].x];ans+=que(ro[bb[j].x],1,n,k-bb[j].z)-que(rot[bb[j].y],1,n,k-bb[j].z);} return ans; } int main(){ int x,y,z;register int j; n=read();m=read(); for (int i=1;i<=n;i++) va[i]=read(); for (int i=1;i<n;i++) x=read(),y=read(),in(x,y),in(y,x); work(1,n,0); int la=0; while(m--){ x=read();y=read();z=read();y^=la;z^=la; if (x){ z-=va[y]; for (register int j=lla[y];j;j=bb[j].ne) in(ro[bb[j].x],1,n,bb[j].z,z),in(rot[bb[j].y],1,n,bb[j].z,z); va[y]+=z; } else printf("%d ",la=qu(y,z)); } }