[文章目录]
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。N,M<=10^5
动态点分治
对于每一个分治的树，线段树维护根到全部深度的点的价值和，再维护到其分治父亲关于深度的价值和。
每次查询计算到根的距离的范围进行查询，多余部分容斥一下即可，修改同理，复杂度
#include <cctype>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 100010
using namespace std;
const int inf=0x3f3f3f3f;
inline char nc()
{
static char buf[100000],*p1,*p2;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
int re=0; char f=0,ch=nc();
while(!isdigit(ch)) {f|=(ch=='-'); ch=nc();}
while(isdigit(ch)) re=re*10+(ch^'0'),ch=nc();
return f ? -re : re;
}
int n,m,val[N],head[N],to[N<<1],nxt[N<<1],cnt,pos[N],dep[N],lca[N<<1][20],Log[N<<1],bin[20],tot;
inline void add(int x,int y)
{
to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt;
to[++cnt]=x; nxt[cnt]=head[y]; head[y]=cnt;
}
inline int Min(int x,int y){return x<y ? x:y;}
inline int Max(int x,int y){return x>y ? x:y;}
void dfs(int x,int pre)
{
lca[++tot][0]=dep[x]=dep[pre]+1;pos[x]=tot;
for(int i=head[x];i;i=nxt[i]) if(to[i]!=pre)
dfs(to[i],x),lca[++tot][0]=dep[x];
}
inline int dis(int x,int y)
{
if(pos[x]>pos[y]) swap(x,y);
int lo=Log[pos[y]-pos[x]+1];//
return dep[x]+dep[y]-(Min(lca[ pos[x] ][lo],lca[ pos[y]-bin[lo]+1 ][lo])<<1);
}
struct seg
{
int ls,rs,s;
}t[N*200];
int se,rt1[N],rt2[N];
void insert(int &rt,int l,int r,int x,int y)
{
if(!rt) rt=++se; t[rt].s+=y;
if(l==r) return ; int mid=(l+r)>>1;
if(x<=mid) insert(t[rt].ls,l,mid,x,y);
else insert(t[rt].rs,mid+1,r,x,y);
}
int query(int rt,int l,int r,int x)
{
if(!rt) return 0;
if(l==r) return t[rt].s;
int mid=(l+r)>>1;
if(x<=mid) return query(t[rt].ls,l,mid,x);
else return t[t[rt].ls].s+query(t[rt].rs,mid+1,r,x);
}
int root,nn,siz[N],msi[N],fa[N],ran[N];
bool vis[N];
void getroot(int x,int pre)
{
siz[x]=1; msi[x]=0;
for(int i=head[x];i;i=nxt[i]) if(!vis[to[i]]&&to[i]!=pre)//
getroot(to[i],x),siz[x]+=siz[to[i]],msi[x]=Max(msi[x],siz[to[i]]);
msi[x]=max(msi[x],nn-siz[x]);
if(msi[x]<msi[root]) root=x;
}
void Dfs(int x,int pre)
{
ran[++tot]=x,siz[x]=1;
for(int i=head[x];i;i=nxt[i]) if(!vis[to[i]]&&to[i]!=pre)
Dfs(to[i],x),siz[x]+=siz[to[i]];
}
void build(int x,int pre)
{
fa[x]=pre; tot=0; Dfs(x,0); vis[x]=1;
for(int i=1;i<=tot;++i) insert(rt1[x],0,n-1,dis(x,ran[i]),val[ran[i]]);
if(pre) for(int i=1;i<=tot;++i) insert(rt2[x],0,n-1,dis(pre,ran[i]),val[ran[i]]);
for(int i=head[x];i;i=nxt[i]) if(!vis[to[i]])
root=0,nn=siz[to[i]],getroot(to[i],x),build(root,x);
}
int main()
{
n=read(); m=read(); int i,j;
for(i=1;i<=n;++i) val[i]=read();
for(i=1;i<n;++i) add(read(),read());
dfs(1,0);
for(Log[1]=0,i=2;i<=tot;++i) Log[i]=Log[i>>1]+1;
for(i=0;i<=Log[tot];++i) bin[i]=1<<i;
for(i=1;i<=Log[tot];++i)
for(j=1;j+bin[i]-1<=tot;++j)
lca[j][i]=Min(lca[j][i-1],lca[j+bin[i-1]][i-1]);
msi[0]=inf,nn=n,getroot(1,0);
build(root,0); int x,y,ans=0;
while(m--)
{
i=read(); x=read()^ans; y=read()^ans;
if(i)
{
for(i=x;i;i=fa[i])
{
insert(rt1[i],0,n-1,dis(x,i),y-val[x]);
if(fa[i]) insert(rt2[i],0,n-1,dis(x,fa[i]),y-val[x]);
}
val[x]=y;
}
else
{
for(ans=0,i=x;i;i=fa[i])
{
if(y>=dis(x,i)) ans+=query(rt1[i],0,n-1,y-dis(x,i));
if(fa[i]&&y>=dis(x,fa[i])) ans-=query(rt2[i],0,n-1,y-dis(x,fa[i]));
}
printf("%d\n",ans);
}
}
return 0;
}