【BZOJ3730】震波
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
HINT
1<=N,M<=100000
1<=u,v,x<=N
1<=value[i],y<=10000
0<=k<=N-1
题解：直接动态树分治，对于每一个分治中心，我们用维护一棵线段树维护它分治子树中的所有节点，下标为节点到分治中心的距离，权值为城市的权值。同时为了防重，还要维护一个从父亲那里减掉的版本。查询时，从当前点一直向父亲移动，每次在线段树中查一下就行了。
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int maxn=100010;
struct node
{
int ls,rs,sum;
}s[maxn*200];
int n,m,cnt,tot,root,mn,ans;
int to[maxn<<1],next[maxn<<1],head[maxn],v[maxn],fa[maxn],siz[maxn],r1[maxn],r2[maxn],vis[maxn],Log[maxn<<1];
int md[20][maxn<<1],pos[maxn],dep[maxn];
void getrt(int x,int fa)
{
siz[x]=1;
int i,tmp=0;
for(i=head[x];i!=-1;i=next[i]) if(!vis[to[i]]&&to[i]!=fa)
getrt(to[i],x),siz[x]+=siz[to[i]],tmp=max(tmp,siz[to[i]]);
tmp=max(tmp,tot-siz[x]);
if(tmp<mn) root=x,mn=tmp;
}
void solve(int x)
{
vis[x]=1;
for(int i=head[x];i!=-1;i=next[i]) if(!vis[to[i]]) tot=siz[to[i]],mn=1<<30,getrt(to[i],x),fa[root]=x,solve(root);
}
void dfs(int x)
{
md[0][++pos[0]]=dep[x],pos[x]=pos[0];
for(int i=head[x];i!=-1;i=next[i]) if(!dep[to[i]]) dep[to[i]]=dep[x]+1,dfs(to[i]),md[0][++pos[0]]=dep[x];
}
inline void add(int a,int b)
{
to[cnt]=b,next[cnt]=head[a],head[a]=cnt++;
}
inline int getmin(int a,int b)
{
if(a>b) swap(a,b);
int k=Log[b-a+1];
return min(md[k][a],md[k][b-(1<<k)+1]);
}
inline int dis(int a,int b)
{
return dep[a]+dep[b]-2*getmin(pos[a],pos[b]);
}
void updata(int l,int r,int &x,int a,int b)
{
if(!x) x=++tot;
s[x].sum+=b;
if(l==r) return ;
int mid=(l+r)>>1;
if(a<=mid) updata(l,mid,s[x].ls,a,b);
else updata(mid+1,r,s[x].rs,a,b);
}
int query(int l,int r,int x,int a,int b)
{
if(!x||a>b) return 0;
if(a<=l&&r<=b) return s[x].sum;
int mid=(l+r)>>1;
if(b<=mid) return query(l,mid,s[x].ls,a,b);
if(a>mid) return query(mid+1,r,s[x].rs,a,b);
return query(l,mid,s[x].ls,a,b)+query(mid+1,r,s[x].rs,a,b);
}
inline char nc(){
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int rd(){
char ch=nc();int sum=0;
while(!(ch>='0'&&ch<='9'))ch=nc();
while(ch>='0'&&ch<='9')sum=sum*10+ch-48,ch=nc();
return sum;
}
int main()
{
//freopen("bz3730.in","r",stdin);
//freopen("bz3730.out","w",stdout);
n=rd(),m=rd();
int a,b,c;
register int i,j,x,y;
memset(head,-1,sizeof(head));
for(i=1;i<=n;i++) v[i]=rd();
for(i=1;i<n;i++) a=rd(),b=rd(),add(a,b),add(b,a);
dep[1]=1,dfs(1),tot=n,mn=1<<30,getrt(1,0),solve(root);
for(i=2;i<=pos[0];i++) Log[i]=Log[i>>1]+1;
for(j=1;(1<<j)<=pos[0];j++) for(i=1;i+(1<<j)-1<=pos[0];i++) md[j][i]=min(md[j-1][i],md[j-1][i+(1<<(j-1))]);
tot=0;
for(i=1;i<=n;i++)
{
x=i;
while(x)
{
y=fa[x],updata(0,n,r1[x],dis(x,i),v[i]);
if(y) updata(0,n,r2[x],dis(y,i),v[i]);
x=y;
}
}
for(i=1;i<=m;i++)
{
c=rd(),a=rd()^ans,b=rd()^ans;
if(!c)
{
ans=0,x=a;
while(x)
{
y=fa[x],ans+=query(0,n,r1[x],0,b-dis(x,a));
if(y) ans-=query(0,n,r2[x],0,b-dis(y,a));
x=y;
}
printf("%d\n",ans);
}
else
{
x=a;
while(x)
{
y=fa[x],updata(0,n,r1[x],dis(x,a),b-v[a]);
if(y) updata(0,n,r2[x],dis(y,a),b-v[a]);
x=y;
}
v[a]=b;
}
}
return 0;
}