题目
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
题解
先构建出来点分树，对于点分树上的每一个节点开两棵线段树，以距离为下标存价值和，维护子树中的点每个距离的到自己的答案$ans$和到父亲的答案$ans’$
修改一路暴跳父亲就可以，查询统计$\sum_{x!=root}ans_{fa_x}-ans’_x$
然而这题要卡常……
- 手写
max函数 - 树剖求$LCA$
- 修改时发现修改位置和值是一样的，所以可以同时修改自己的$ans’$和父亲的$ans$
- 查询同理
- ……
当你在本地跑进$1s$的时候$BZOJ$就可能能过了
写代码$10$分钟卡常卡了$1$个多小时……
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
# define tl s[k].l
# define tr s[k].r
# define mid (l+r>>1)
# define X first
# define Y second
# 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*35];
int n,m,num,cnt,rt,Sum,tot;
int h[MAX],val[MAX],F[MAX],Rt[MAX],id[MAX],f[MAX],fa[MAX],siz[MAX],son[MAX],top[MAX],d[MAX];
bool use[MAX];
int read()
{
int x(0);
char ch=getchar();
for(;!isdigit(ch);ch=getchar());
for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
return x;
}
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=1)
{
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,id[x]=++cnt;
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);}
Pi operator+ (Pi a,Pi b) {return mp(a.X+b.X,a.Y+b.Y);}
Pi ask(int l,int r,int k,int _k,int L,int R)
{
if(r<L||R<l||(!k&&!_k)) return mp(0,0);
if(l>=L&&r<=R) return mp(s[k].x,s[_k]._x);
return ask(l,mid,tl,s[_k].l,L,R)+ask(mid+1,r,tr,s[_k].r,L,R);
}
void change(int l,int r,int &k,int x,int dis)
{
if(!k) k=++tot;
s[k].x+=dis;
if(l==r) return;
if(x<=mid) change(l,mid,tl,x,dis);
else change(mid+1,r,tr,x,dis);
}
void change(int l,int r,int &k,int &_k,int x,int dis)
{
if(!k) k=++tot;
if(!_k) _k=++tot;
s[k]._x+=dis,s[_k].x+=dis;
if(l==r) return;
if(x<=mid) change(l,mid,tl,s[_k].l,x,dis);
else change(mid+1,r,tr,s[_k].r,x,dis);
}
void change(int x,int dis)
{
change(1,n,Rt[x],1,dis);
for(int i=x,d;F[i];i=F[i])
d=GET_DIS(x,F[i]),change(1,n,Rt[i],Rt[F[i]],d+1,dis);
}
int ask(int x,int k)
{
Pi A;
int ans=(A=ask(1,n,Rt[x],0,1,k+1)).X;
for(int i=x,d;F[i];i=F[i])
{
d=GET_DIS(x,F[i]);
if(d<=k) A=ask(1,n,Rt[F[i]],Rt[i],1,k-d+1),ans+=A.X-A.Y;
}
return ans;
}
int main()
{
n=read(),m=read();
for(int i=1;i<=n;++i)
val[i]=read();
for(int i=1,x;i<n;++i)
x=read(),add(x,read());
dfs_(),dfs__(),Sum=f[rt=0]=n,dfs();
for(int i=1;i<=n;++i)
change(i,val[i]);
for(int i=1,ans=0,op,x,y;i<=m;++i)
{
op=read(),x=read()^ans,y=read()^ans;
if(!op) printf("%d\n",ans=ask(x,y));
else if(op==1) change(x,y-val[x]),val[x]=y;
}
return 0;
}
