2022.03.11点分树

2022.03.11 点分树

2.1 前置知识

2.1.1 点分治

点分治是每次选择子树中的重心不断更新答案的东西。

对于父节点x和子节点y，\(dis(x,y)=k\)，可以先以x为子树中的根节点计算出除它自己外子树中任意两个节点u、v的dis。不过如果u、v的lca是y，那么相当于多计算了两遍从x到y，对此减去……抱歉，我还不会。

可以参考

https://blog.csdn.net/qq_39553725/article/details/77542223

2.2 点分树

2.2.1 点分树

https://www.cnblogs.com/Xing-Ling/p/12976848.html

https://www.cnblogs.com/liuchanglc/p/14282204.html

把每次分治的重心连起来，就是一颗树。这棵树叫点分树。

因为是重心，所以树高不超过\(logn\)。一个新树上的子树表示它原本树上的连通块。所以原树上任意两点x、y在新树上的lca在原树上x到y的路径上，即\(dis(x,y)=dis(x,lca)+dis(lca,y)\)。

2.2.2 P6329 【模板】点分树 | 震波（点分树模板）

https://www.luogu.com.cn/problem/P6329

//https://www.luogu.com.cn/blog/SHEEP-BOLG/post-ti-xie-p6329-mu-ban-dian-fen-shu-zhen-bo #include<bits/stdc++.h>using namespace std;const int N=2e5+10;int n,m,cnt,head[N],val[N],root,sizei[N],maxn[N],vis[N];int tot,ind,fa[N],dep[N],true_id[N],f[N<<1][21],logi[N<<1];struct node{	int to,next;}a[N<<1];vector<int>t[2][N];inline int read(){	int s=0,w=1;	char ch=getchar();	while(ch<'0'||ch>'9'){		if(ch=='-')w=-1;		ch=getchar();	}	while(ch<='9'&&ch>='0'){		s=s*10+ch-'0';		ch=getchar();	}	return s*w;}inline void add(int u,int v){	++cnt;	a[cnt].to=v;	a[cnt].next=head[u];	head[u]=cnt;}inline void pre(int x,int fai){	f[++ind][0]=x;true_id[x]=ind;	for(int i=head[x];i;i=a[i].next){		int v=a[i].to;		if(v==fai)continue;		dep[v]=dep[x]+1;		pre(v,x);		f[++ind][0]=x;	}}inline int depmin(int x,int y){	return dep[x]<dep[y]?x:y;}inline void ST(){	logi[0]=0;logi[1]=0;logi[2]=1;	for(int i=3;i<=ind;i++)logi[i]=logi[i/2]+1;	/*cout<<"true_id "<<endl;	for(int i=1;i<=n;i++)cout<<true_id[i]<<" ";cout<<endl;	cout<<"f 0 "<<endl;	for(int i=1;i<=ind;i++)cout<<f[i][0]<<" ";cout<<endl;	cout<<"dep "<<endl;	for(int i=1;i<=n;i++)cout<<dep[i]<<" ";cout<<endl;	cout<<"logi "<<endl;	for(int i=1;i<=ind;i++)cout<<logi[i]<<" ";cout<<endl;*/ 	for(int i=1;(1<<i)<=ind;i++)	for(int j=1;j+(1<<(i-1))-1<=ind;j++)	f[j][i]=depmin(f[j][i-1],f[j+(1<<(i-1))][i-1]);	/*cout<<"f total "<<endl;	for(int i=1;i<=ind;i++){		for(int j=0;j<=ind;j++)cout<<f[i][j]<<" ";		cout<<endl;	}*/ }inline int Dis(int x,int y){	if(true_id[x]>true_id[y])swap(x,y);	int xi=true_id[x],yi=true_id[y];	int k=logi[yi-xi+1];	int lca=depmin(f[xi][k],f[yi-(1<<k)+1][k]);	return dep[x]+dep[y]-2*dep[lca];	//dis(x,y)=dis(xi,lca)+dis(lca,yi)	//这么写似乎是为了不重构点分树	//对于x第一次出现到y第一次出现中间出现的所有数都是	//x在原树上所出现的子树与y在原树上所出现的子树中间的节点，	//中间dep的最小值就是lca的深度，	//所以查lca直接查询中间dep最小的节点的名称 }inline int lowbit(int x){	return x&-x;}inline void update(int flag,int indi,int x,int vali){	++x;	for(int i=x;i<=sizei[indi];i+=lowbit(i))t[flag][indi][i]+=vali;}inline int query(int flag,int indi,int x){	++x;x=min(x,sizei[indi]);	int fin=0;	for(int i=x;i;i-=lowbit(i))fin+=t[flag][indi][i];	return fin;}inline void height(int x,int fai){	sizei[x]=1;maxn[x]=0;	for(int i=head[x];i;i=a[i].next){		int v=a[i].to;		if(v==fai||vis[v])continue;		height(v,x);		sizei[x]+=sizei[v];		maxn[x]=max(maxn[x],sizei[v]);	}	maxn[x]=max(maxn[x],tot-sizei[x]);	if(maxn[x]<maxn[root])root=x;}inline void divide(int x){	vis[x]=1;	sizei[x]=tot+1;	t[0][x].resize(sizei[x]+1);	t[1][x].resize(sizei[x]+1);	for(int i=head[x];i;i=a[i].next){		int v=a[i].to;		if(vis[v])continue;		tot=sizei[v];maxn[0]=n;root=0;		height(v,x);		fa[root]=x;		divide(root);	}}inline void change(int x,int vali){	for(int i=x;i;i=fa[i])update(0,i,Dis(x,i),vali);	//0是x节点对以i节点为根的子树的影响 	for(int i=x;fa[i];i=fa[i])update(1,i,Dis(x,fa[i]),vali);	//1是x节点对以fa[i]为根的子树的影响 }signed main(){	n=read();m=read();	for(int i=1;i<=n;i++)val[i]=read();	for(int i=1;i<n;i++){		int u,v;		u=read();v=read();		add(u,v);add(v,u);	}	pre(1,0);	ST();	tot=n;maxn[0]=n;root=0;	height(1,0);	divide(root);	for(int i=1;i<=n;i++)change(i,val[i]);	int lasti=0;	for(int i=1;i<=m;i++){		int op,x,y;		op=read();x=read();y=read();		x^=lasti;y^=lasti;		if(op==1){			change(x,y-val[x]);			val[x]=y;		}else if(op==0){			//cout<<"Case 1 "<<endl;			lasti=query(0,x,y);			//cout<<"Case 2 "<<endl;			for(int i=x;fa[i];i=fa[i]){				int u=Dis(x,fa[i]);				if(y>=u)lasti+=query(0,fa[i],y-u)-query(1,i,y-u);				//这里请参考eleveni的神奇想法：				//宝石那题一层一层往上蹦着记录fa[i]对答案的贡献				//减去fa[i]已经被计算过的子树的贡献 			}			cout<<lasti<<endl;		}	}	return 0;}

2.2.3 P6626 [省选联考 2020 B 卷] 消息传递(简化版模板)

https://www.luogu.com.cn/problem/P6626

30pts：暴力+线段树

我执意要把一个父亲一个父亲蹦的代码搞上来，然后它TLE了……

#include<bits/stdc++.h>using namespace std;const int N=1e5+10;int T,n,m,cnt,head[N],dep[N],ans;struct node{	int to,next;}a[N<<1];inline int read(){	int s=0,w=1;	char ch=getchar();	while(ch<'0'||ch>'9'){		if(ch=='-')w=-1;		ch=getchar();	}	while(ch<='9'&&ch>='0'){		s=s*10+ch-'0';		ch=getchar();	}	return s*w;}inline void add(int u,int v){	++cnt;	a[cnt].to=v;	a[cnt].next=head[u];	head[u]=cnt;}inline void dfs(int x,int fai,int k){	dep[x]=dep[fai]+1;	if(dep[x]==k)++ans;	for(int i=head[x];i;i=a[i].next){		int v=a[i].to;		if(v==fai)continue;		dfs(v,x,k);	}}inline void solve1(){	for(int i=1;i<=m;i++){		ans=0;		int x,k;		x=read();k=read();		dfs(x,0,k+1);		cout<<ans<<endl;	}}#define lson(x) (x)<<1#define rson(x) (x)<<1|1int ind,id_true[N],true_id[N],sizei[N],fa[N];struct tree{	int L,R,val;}t[N<<4];inline void update(int x){	t[x].val=max(t[lson(x)].val,t[rson(x)].val);}inline void build(int x,int l,int r){	t[x].L=l;t[x].R=r;	if(l==r)return (void)(t[x].val=dep[id_true[l]]);	int mid=(l+r)>>1;	build(lson(x),l,mid);	build(rson(x),mid+1,r);	update(x);}inline int query(int x,int l,int r,int L,int R,int k){	if(l==r)return t[x].val==k;	if(l>=L&&r<=R){		if(t[x].val<k)return 0;	}	if(r<L||l>R)return 0;	int mid=(l+r)>>1;	int fin=0;	if(L<=mid)fin+=query(lson(x),l,mid,L,R,k);	if(R>mid)fin+=query(rson(x),mid+1,r,L,R,k);	return fin;}inline void dfs2(int x,int fai){	dep[x]=dep[fai]+1;	fa[x]=fai;	sizei[x]=1;	id_true[++ind]=x;	true_id[x]=ind;	for(int i=head[x];i;i=a[i].next){		int v=a[i].to;		if(v==fai)continue;		dfs2(v,x);		sizei[x]+=sizei[v];	}}inline void find(){	cout<<"tree "<<endl;	for(int i=1;i<=8;i++)	cout<<i<<" L "<<t[i].L<<" R "<<t[i].R<<" val "<<t[i].val<<endl;}inline void solve2(){	ind=0;	memset(id_true,0,sizeof(id_true));	memset(true_id,0,sizeof(true_id));	memset(fa,0,sizeof(fa));	memset(dep,0,sizeof(dep));	memset(sizei,0,sizeof(sizei));	dfs2(1,0);	build(1,1,ind);	for(int i=1;i<=m;i++){		int x,k;		x=read();k=read();		ans=0;		int u=true_id[x],v=true_id[x]+sizei[x]-1;		ans=query(1,1,ind,u,v,k);		for(int i=fa[x],j=1;i&&j<=k;i=fa[i],j++){			int ui=true_id[i];			int vi=ui+sizei[i]-1;			if(ui<=u-1)ans+=query(1,1,ind,ui,u-1,k);			if(vi>=v+1)ans+=query(1,1,ind,v+1,vi,k);			u=ui,v=vi;		}		cout<<ans<<endl;	}}signed main(){	T=read();	while(T--){		memset(head,0,sizeof(head));		cnt=0;		memset(a,0,sizeof(a));		n=read();m=read();		for(int i=1;i<n;i++){			int u,v;			u=read();v=read();			add(u,v);add(v,u);		}		if(n<=2e3&&m<=2e3)solve1();		else solve2();	}	return 0;}

100pts：点分树

好家伙，连修改都不用，直接上来怼！

#include<bits/stdc++.h>using namespace std;const int N=1e5+10;int n,T,m,cnt,head[N],dep[N];int tot,root,sizei[N],maxn[N],vis[N];int fa[N],ind,f[N<<1][21],true_id[N],logi[N<<1];struct node{	int to,next;}a[N<<1];vector<int>t[2][N];inline int read(){	int s=0,w=1;	char ch=getchar();	while(ch<'0'||ch>'9'){		if(ch=='-')w=-1;		ch=getchar();	}	while(ch<='9'&&ch>='0'){		s=s*10+ch-'0';		ch=getchar();	}	return s*w;}inline void add(int u,int v){	++cnt;	a[cnt].to=v;	a[cnt].next=head[u];	head[u]=cnt;}inline void pre(int x,int fai){	dep[x]=dep[fai]+1;	f[++ind][0]=x;	true_id[x]=ind;	for(int i=head[x];i;i=a[i].next){		int v=a[i].to;		if(v==fai)continue;		pre(v,x);		f[++ind][0]=x;	}}inline void height(int x,int fai){	sizei[x]=1;maxn[x]=0;	for(int i=head[x];i;i=a[i].next){		int v=a[i].to;		if(v==fai||vis[v])continue;		height(v,x);		sizei[x]+=sizei[v];		maxn[x]=max(maxn[x],sizei[v]);	}	maxn[x]=max(maxn[x],tot-sizei[x]);	if(maxn[x]<maxn[root])root=x;}inline void findsizei(int x,int fai){	sizei[x]=1;	for(int i=head[x];i;i=a[i].next){		int v=a[i].to;		if(v==fai||vis[v])continue;		findsizei(v,x);		sizei[x]+=sizei[v];	}}inline void divide(int x){	vis[x]=1;	//findsizei(x,0);	sizei[x]=tot+1;	t[0][x].resize(sizei[x]+1);	t[1][x].resize(sizei[x]+1);	for(int i=head[x];i;i=a[i].next){		int v=a[i].to;		if(vis[v])continue;		tot=sizei[v];maxn[0]=n;root=0;		height(v,x);		fa[root]=x;		divide(root);	}}inline int depmin(int x,int y){	return dep[x]<dep[y]?x:y;}inline void ST(){	logi[2]=1;	for(int i=3;i<=ind;i++)logi[i]=logi[i/2]+1;	for(int i=1;(1<<i)<=ind;i++)	for(int j=1;j+(1<<(i-1))-1<=ind;j++)	f[j][i]=depmin(f[j][i-1],f[j+(1<<(i-1))][i-1]);}inline int Dis(int x,int y){	if(true_id[x]>true_id[y])swap(x,y);	int xi=true_id[x],yi=true_id[y];	int k=logi[yi-xi+1];	int lca=depmin(f[xi][k],f[yi-(1<<k)+1][k]);	return dep[x]+dep[y]-2*dep[lca];}inline int lowbit(int x){	return x&-x;}inline void update(int x,int vali){	++t[0][x][0];	for(int i=x;fa[i];i=fa[i]){		int disi=Dis(x,fa[i]);		++t[0][fa[i]][disi];		++t[1][i][disi];	}}inline int query(int x,int k){	int fin=0;	if(sizei[x]>=k)fin=t[0][x][k];	for(int i=x;fa[i];i=fa[i]){		int disi=Dis(x,fa[i]);		if(disi>k||(k-disi)>sizei[fa[i]])continue;		fin+=t[0][fa[i]][k-disi];		if(sizei[i]>=k-disi)fin-=t[1][i][k-disi];	}	return fin;}inline void init(){	memset(true_id,0,sizeof(true_id));	memset(sizei,0,sizeof(sizei));	memset(head,0,sizeof(head));	memset(maxn,0,sizeof(maxn));	memset(dep,0,sizeof(dep));	memset(vis,0,sizeof(vis));	memset(fa,0,sizeof(fa));	memset(a,0,sizeof(a));	memset(f,0,sizeof(f));	for(int i=1;i<=n;i++)	t[0][i].erase(t[0][i].begin(),t[0][i].end()),	t[1][i].erase(t[1][i].begin(),t[1][i].end());	cnt=ind=tot=0;}signed main(){	T=read();	while(T--){		init();		n=read();m=read();		for(int i=1;i<n;i++){			int u,v;			u=read();v=read();			add(u,v);add(v,u);		}		pre(1,0);		ST();		tot=n;maxn[0]=n;root=0;		height(1,0);		divide(root);		for(int i=1;i<=n;i++)update(i,1);		for(int i=1;i<=m;i++){			int x,k;			x=read();k=read();			int ans=query(x,k);			cout<<ans<<endl;		}	}	return 0;}/*24 21 22 33 41 12 24 21 22 33 41 12 2*/