点分治与点分树学习笔记

2023-12-25 13:58:40

一、引入

我们看这样的一道题：给定一棵有\(m\)的点的树，询问树上是否存在距离为\(k\)的点对，有\(m\)组询问，\(nm\le 10^6\).

容易想到的做法是暴力，即对于每一个点对都暴力判断，显然，它的时间复杂度不够优秀。

点分治，就是解决像这道题一样需要大规模处理树上路径的问题的一种好方法。

二、算法流程

考虑这样的情况，我们面对的并不是一棵树，而是一个序列的是有关区间的区间和之类的问题。

对于这样的问题，我们知道可以通过选中点，分治处理左右部分，然后单独考虑跨过中点的区间的贡献，而处理后者往往比处理原问题容易地多。

我们希望将这样的分治策略扩展的树上，但我们该如何定义树上的中点呢？

这里我们引入一个概念——树的重心

它的定义是：在一棵树上，找到一个点，使以这个点作为根时，所有子树中大小最大的一个的大小最小(一棵子树的大小就是这棵子树的节点个数)，那么这个点就是重心。

根据定义，一旦我们选择重心，然后递归处理每一棵子树，每一棵子树的大小都不会超过原树的\(\frac 12\)，这保证了点分治的复杂度。

于是，我们就能写出算法流程了：

1.找到重心
2.处理经过重心的路径的贡献
3.递归处理重心的所有子树

三、实现

寻找重心部分：

int rt,mxsiz;
inline void getsiz(int u,int f){
	siz[u]=1;
	for(int i=first[u];i;i=e[i].nxt){
		int v=e[i].v;
		if(v==f||vis[v]) continue;
		getsiz(v,u);siz[u]+=siz[v];
	}
	return ;
}
int dis[N],d[N];
inline void findrt(int u,int f,int sum){//sum是目前正在处理的这棵子树的大小
	int mx=sum-siz[u];
	for(int i=first[u];i;i=e[i].nxt){
		int v=e[i].v;
		if(v==f||vis[v]) continue;//vis是对已经选择过的重心打的标记，这样就能防止遍历到其他子树上	
		findrt(v,u,sum);
		mx=max(mx,siz[v]);
	}
	if(mx<mxsiz) mxsiz=mx,rt=u;
}

接下来是分治的实现方式：

首先先找到重心，然后标记重心以防遍历子树时通过重心跑到另一个子树上

然后处理经过重心的路径，也就是这里的\(calc(rt)\)，\(calc\)是每道题目都不相同的函数。

一般实现方式是：依次遍历子树，增加这棵子树中的点和已经遍历过的点的贡献

inline void solve(int u){
	rt=0;mxsiz=0x3f3f3f3f;sz=0;
	getsiz(u,0);
	findrt(u,0,siz[u]);
	vis[rt]=1;
	ans+=calc(rt);
	for(int i=first[rt];i;i=e[i].nxt){
		int v=e[i].v;
		if(vis[v]) continue;
		solve(v);
	}
}

接下来我们通过例题来讲解\(calc\)函数的\(2\)种实现方式：

四、例题

洛谷模板题

这就是我们在引入中所提到的题目。

我们可以开一个数组记录已经遍历过的节点到根的距离，增加一棵子树时，就依次考虑这棵树中所有节点到根的距离\(d\)，并判断一下是否已经有距离为\(k-d\)的点即可：

#include<bits/stdc++.h>
using namespace std;
const int M=1e7+10;
const int N=2e5+10;
int n,m,k,rt,sz,mxsiz,mxk,ans=0,vis[N],siz[N],cnt,first[N],w[M],K[N],anss[N];
struct node{
	int v,w,nxt;
}e[N<<1];
inline void add(int u,int v,int w){e[++cnt].v=v;e[cnt].w=w;e[cnt].nxt=first[u];first[u]=cnt;}
inline void getsiz(int u,int f){
	siz[u]=1;
	for(int i=first[u];i;i=e[i].nxt){
		int v=e[i].v;
		if(v==f||vis[v]) continue;
		getsiz(v,u);siz[u]+=siz[v];
	}
	return ;
}
int dis[N],d[N];
inline void findrt(int u,int f,int sum){
	int mx=sum-siz[u];
	for(int i=first[u];i;i=e[i].nxt){
		int v=e[i].v;
		if(v==f||vis[v]) continue;	
		findrt(v,u,sum);
		mx=max(mx,siz[v]);
	}
	if(mx<mxsiz) mxsiz=mx,rt=u;
}
inline void getdis(int u,int f){
	dis[++sz]=d[u];
	for(int i=first[u];i;i=e[i].nxt){
		int v=e[i].v;
		if(v==f||vis[v]) continue;
		d[v]=d[u]+e[i].w;
		getdis(v,u);
	}
}
inline void calc(int u){
	vector<int> used; 
	w[0]=1;
	for(int i=first[u];i;i=e[i].nxt){
		int v=e[i].v;
		if(vis[v]) continue;
		sz=0;d[v]=e[i].w;
		getdis(v,u);
		for(int t=1;t<=m;++t){
			if(anss[t]) continue;
			for(int j=1;j<=sz;++j){
				if(dis[j]>K[t]) continue;
				if(w[K[t]-dis[j]]){
					anss[t]=1;
					break;
				}
			}
		}
		for(int j=sz;j>0;j--)
			if(dis[j]<=mxk) used.push_back(dis[j]),w[dis[j]]=1;
	}
	for(int i=0;i<used.size();++i) w[used[i]]=0;
}
inline void solve(int u){
	rt=0;mxsiz=0x3f3f3f3f;sz=0;
	getsiz(u,0);
	findrt(u,0,siz[u]);
	vis[rt]=1;
	calc(rt);
	for(int i=first[rt];i;i=e[i].nxt){
		int v=e[i].v;
		if(vis[v]) continue;
		solve(v);
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1,u,v,w;i<n;++i){
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);add(v,u,w);
	}
	for(int i=1;i<=m;++i) scanf("%d",&K[i]),mxk=max(mxk,K[i]);
	solve(1);
	for(int i=1;i<=m;++i)
		if(anss[i]) puts("AYE");
		else puts("NAY"); 
	return 0;
}

聪聪可可

依然没有什么区别，不过这次我们只关心路径长度\(\%3\)的余数：

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,m,k,rt,sz,mmx,mxk,ans=0,vis[N],siz[N],cnt,first[N],w[3];
struct node{
	int v,w,nxt;
}e[N<<1];
inline void add(int u,int v,int w){e[++cnt].v=v;e[cnt].w=w;e[cnt].nxt=first[u];first[u]=cnt;}
inline void getsiz(int u,int f){
	siz[u]=1;
	for(int i=first[u];i;i=e[i].nxt){
		int v=e[i].v;
		if(v==f||vis[v]) continue;
		siz[u]+=siz[v];
	}
	return ;
}
int dis[N],d[N];
inline void findrt(int u,int f,int sum){
	int mx=sum-siz[u];
	for(int i=first[u];i;i=e[i].nxt){
		int v=e[i].v;
		if(v==f||vis[v]) continue;	
		findrt(v,u,sum);
		mx=max(mx,siz[v]);
	}
	if(mx<mmx) mmx=mx,rt=u;
}
inline void getdis(int u,int f){
	dis[++sz]=d[u];
	for(int i=first[u];i;i=e[i].nxt){
		int v=e[i].v;
		if(v==f||vis[v]) continue;
		d[v]=d[u]+e[i].w;
		getdis(v,u);
	}
}
inline void calc(int u){
	vector<int> used; 
	w[0]=1;w[1]=w[2]=0;
	for(int i=first[u];i;i=e[i].nxt){
		int v=e[i].v;
		if(vis[v]) continue;
		sz=0;d[v]=e[i].w;
		getdis(v,u);
		for(int j=1;j<=sz;++j) ans+=w[(3-(dis[j]%3))%3];
		for(int j=1;j<=sz;++j) w[dis[j]%3]++;
	}
}
inline void solve(int u){
	rt=0;mmx=0x3f3f3f3f;sz=0;
	getsiz(u,0);
	findrt(u,0,siz[u]);
	vis[rt]=1;
	calc(rt);
	for(int i=first[rt];i;i=e[i].nxt){
		int v=e[i].v;
		if(vis[v]) continue;
		solve(v);
	}
}
int main(){
	scanf("%d",&n);
	for(int i=1,u,v,w;i<n;++i){
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);add(v,u,w);
	}
	solve(1);
	int fz=ans*2+n,fm=n*n,g=__gcd(fz,fm);
	printf("%d/%d\n",fz/g,fm/g);
	return 0;
}

至此，大家大概已经理解点分治的原理和实现了，接下来我们再介绍一下点分树，又叫动态点分治：

未完待续。。。

码农公寓