Tony Zhao

题目大意

请你维护一棵每个点有点权，边权全为1的树，支持以下操作：

求与X距离不超过K的点的权值和。
修改点X的权值。

动态点分治第一题= =

动态点分治是动态维护点分治的算法。点分治的时候求出的每一个点都对应一棵子树，所以我们将范围大的点到范围小的点连边得到一颗新树，树上保证父亲节点对应的分治子树包含子节点对应的分治子树。

这道题在每一个点上维护一颗线段树，线段树上记录着分治子树中距该点距离为i的点的权值和。之后对于每个点的单点修改就在所有包含它的树点对应的线段树中进行修改。对于查询操作就查询一下所有与该点有关的树的相关信息求和就好了。

注意这题一段区间如果暴力求的话肯定会出现重复计算的情况的……所以需要进行容斥。具体方法就是自底向上进行查询的时候如果一个点在上一层也被包含了那就删除这个点在这次的计算结果，用另一颗线段树记录如果父树也被选中了子树要干掉多少。

(P.S.在这里我的代码进行了一次失败的尝试……码丑勿喷qwq

#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
#define RE register
#define N 100010
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 RI()
{
	RE int ret=0;RE char tmp=nc();
	while(!isdigit(tmp)) tmp=nc();
	while(isdigit(tmp)) ret=ret*10+(tmp^'0'),tmp=nc();
	return ret;
}
int n,m,v[N],lg[N<<1],rk[N],md[20][N<<1],depth[N],siz[N],cnt,ms[N],ts,rt,tp,fa[N],sum[N*200],ls[N*200],rs[N*200],ra[N],rb[N];
int to[N<<1],nxt[N<<1],head[N],tot;
bool vis[N];
inline void AE(RE int X,RE int Y){to[++tot]=Y,nxt[tot]=head[X],head[X]=tot;}
inline void DFS(RE int POS,RE int PRE)
{
	rk[POS]=++cnt,md[0][cnt]=depth[POS];
	for(RE int i=head[POS];i;i=nxt[i]) if(to[i]!=PRE) depth[to[i]]=depth[POS]+1,DFS(to[i],POS),md[0][++cnt]=depth[POS];
}
inline void getroot(RE int POS,RE int PRE)
{
	siz[POS]=1,ms[POS]=0;
	for(RE int i=head[POS];i;i=nxt[i]) if(to[i]!=PRE&&!vis[to[i]]) getroot(to[i],POS),siz[POS]+=siz[to[i]],ms[POS]=max(ms[POS],siz[to[i]]);//vis[i] Point'i'IsEliminated
	ms[POS]=max(ms[POS],ts-siz[POS]);
	if(ms[POS]<ms[rt]) rt=POS;
}
inline void update(RE int &POS,RE int L,RE int R,RE int X,RE int V)
{
	if(!POS) POS=++tp;
	sum[POS]+=V;
	if(L==R) return;
	RE int MID=(L+R)>>1;
	if(X<=MID) update(ls[POS],L,MID,X,V);
	else update(rs[POS],MID+1,R,X,V);
}
inline int query(RE int POS,RE int L,RE int R,RE int X)
{
	if(!POS) return 0;
	if(L==R) return sum[POS];
	RE int MID=(L+R)>>1;
	if(X<=MID) return query(ls[POS],L,MID,X);
	else return sum[ls[POS]]+query(rs[POS],MID+1,R,X);
}
inline int dis(RE int X,RE int Y)
{
	RE int ret=depth[X]+depth[Y];
	X=rk[X],Y=rk[Y];
	if(X>Y) swap(X,Y);
	RE int tmp=lg[Y-X+1];
	return ret-(min(md[tmp][X],md[tmp][Y-(1<<tmp)+1])<<1);
}
inline void apply(RE int POS,RE int PRE,RE int P)//P RootOfTheDivideTree
{
	update(ra[P],0,n-1,dis(POS,P),v[POS]);
	if(fa[P]) update(rb[P],0,n-1,dis(POS,fa[P]),v[POS]);//rb[P] TheAmountIncludedInTheTreeWithRoot'fa[P]'
	siz[POS]=1;
	for(RE int i=head[POS];i;i=nxt[i]) if(to[i]!=PRE&&!vis[to[i]]) apply(to[i],POS,P),siz[POS]+=siz[to[i]];
}
inline void divide(RE int POS)
{
	apply(POS,0,POS),vis[POS]=true;
	for(RE int i=head[POS];i;i=nxt[i]) if(!vis[to[i]]) rt=0,ts=siz[to[i]],getroot(to[i],0),fa[rt]=POS,divide(rt);//fa[i] FatherInTheDivideTree
}
inline int request(RE int POS,RE int K)
{
	RE int ret=0;
	for(RE int i=POS;i;i=fa[i])
	{
		if(dis(POS,i)<=K) ret+=query(ra[i],0,n-1,K-dis(POS,i));
		if(fa[i]&&dis(POS,fa[i])<=K) ret-=query(rb[i],0,n-1,K-dis(POS,fa[i]));
	}
	return ret;
}
inline void modify(int X,int Y)
{
	for(RE int i=X;i;i=fa[i])
	{
		update(ra[i],0,n-1,dis(X,i),Y-v[X]);
		if(fa[i]) update(rb[i],0,n-1,dis(X,fa[i]),Y-v[X]);
	}
	v[X]=Y;
}
int main()
{
	RE int X,Y,MD,LA=0;
	n=RI(),m=RI();
	for(RE int i=1;i<=n;++i) v[i]=RI();
	for(RE int i=2;i<=n;++i) X=RI(),Y=RI(),AE(X,Y),AE(Y,X);
	DFS(1,0);
	for(RE int i=2;i<=cnt;++i) lg[i]=lg[i>>1]+1;
	for(RE int i=1;(1<<i)<=cnt;++i) for(RE int j=1;j<=cnt-(1<<i)+1;++j) md[i][j]=min(md[i-1][j],md[i-1][j+(1<<(i-1))]);//md[i]:MinimumDepth
	ms[0]=1<<30,ts=n,getroot(1,0),divide(rt);//ms[i]:MaximumSize ts:TotSizeOfTheSubtree rt:Root
	while(m--)
	{
		MD=RI(),X=RI()^LA,Y=RI()^LA;
		if(!MD) printf("%d\n",LA=request(X,Y));
		else modify(X,Y);
	}
	return 0;
}

BZOJ 3730 震波

题目大意