P3806 【模板】点分治 1 题解

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-05-13 08:40:54

什么是点分治

当一道树上题目可以离线，想要求得子树内或路径上的某些信息时，就可以使用点分治。

来看这道题目。

题目描述

给定一棵有 $n$ 个点的树，询问树上距离为 $k$ 的点对是否存在。

对于 $100\%$ 的数据，保证 $1 \leq n\leq 10^4$，$1 \leq m\leq 100$，$1 \leq k \leq 10^7$，$1 \leq u, v \leq n$，$1 \leq w \leq 10^4$。

做法

暴力做法非常简单，我们先把询问离线下来，然后用 $O(n^2)$ 去枚举两个点 $u,v$，利用树上差分求解，总时间复杂度 $O(n^2\log n)$。

我们考虑以 $u$ 为根的子树内路径都有哪些情况，发现只有两类：

经过树的根 $u$，
不经过树根，在某棵子树内

不难发现，对于第二种情况，我们可以在子树内某个点为树根时统计到它的贡献，因此我们只需要考虑如何计算第一种情况。

首先我们需要求出子树内每个点到根的距离，在这里使用 $d$ 数组表示，这样我们就可以使用两条路径拼成一条长的路径。

\/\/统计出每个点路径长度
int cnt;
int dis[maxn],d[maxn];
void getdep(int u,int fa)
{
	dis[++cnt] = d[u];
	for(auto nxt : G[u])
	{
		int v = nxt.v;
		int w = nxt.w;
		if(v == fa || vis[v]) continue;
		d[v] = d[u] + w;
		getdep(v,u);
	}
}

但是如果两个点 $u,v$ 在树根的同一棵子树内，那么就会产生前面的第二种情况，也就是与自己子树内的点计算贡献。因此我们考虑在计算完当前点与之前点的贡献后，再统一把这棵子树的距离值加进去。

我们使用一个 $dis$ 数组来记录当前树上已经遍历过的路径长度，那么我们每次计算完路径长度，就可以统计答案。

具体的，外层循环枚举路径长度，内层枚举每个询问。
我们令 $dis[i]$ 表示当前枚举的路径长度，$k$ 表示当前询问的长度，那么我们需要查询长度为 $k - dis[i]$ 的路径是否存在，使用一个桶记录一下就好。

int q[maxn];\/\/队列 存储当前子树内产生贡献的点 
bool judge[10000010];\/\/判断一个数是否存在 

void getans(int u)
{
	judge[0] = 1;\/\/长度为0的路径存在，目的是统计长度为k的路径
	int p = 0;\/\/队列长度
	for(auto nxt : G[u])
	{
		int v = nxt.v;
		int w = nxt.w;
		if(vis[v]) continue;
		cnt = 0;\/\/记录路径数量
		d[v] = w;
		getdep(v,u);
		for(int i = 1;i <= cnt;i++)
			for(int j = 1;j <= m;j++)
				if(que[j] >= dis[i]) ans[j] |= judge[que[j] - dis[i]];\/\/统计答案
				
		for(int i = 1;i <= cnt;i++)
		{
			if(dis[i] <= 1e7)
			{
				judge[dis[i]] = 1;
				q[++p] = dis[i];\/\/加入队列
			}
		}
	}
	for(int i = 1;i <= p;i++) judge[q[i]] = 0;\/\/全部处理完后要清空
}

要注意，当我们处理完所有子树后，对根的分治就完成了，此时为了避免当前子树内的路径对其它子树产生贡献，我们需要清空它的贡献。注意不要使用 memset，否则时间复杂度就假了。

由于我们需要递归的去做，所以复杂度是和树的深度与子树大小密切相关的，因此我们需要找出一种最优的方案，来减少递归。

在树型结构中，重心具有很多优秀的性质，删掉重心后，其他的子树都尽可能地保持平衡，最大子树大小最小。

因此我们对一棵子树，选择重心进行点分治，这样对于整棵树，只需要进行 $O(\log n)$ 次。

int siz[maxn],f[maxn];\/\/siz子树大小，f最大子树 
int vis[maxn];\/\/表示每个点是否已经被分治过 

\/\/求重心 
void getroot(int u,int fa)
{
	siz[u] = 1;
	f[u] = 0;
	for(auto nxt : G[u])
	{
		int v = nxt.v;
		int w = nxt.w;
		if(vis[v] || v == fa) continue;
		getroot(v,u);
		siz[u] += siz[v];
		f[u] = max(f[u],siz[v]);
	}
	f[u] = max(f[u],s - siz[u]);
	if(f[u] < f[rt]) rt = u;
}

到这里基本已经完成了，接下来只需要完善一下分治以及主函数即可。

我们发现点分治大致有四个步骤：

求出当前子树重心
求出子树内点到重心的距离
统计答案、清空
向下分治

到这里，我们已经做完了这道点分治模板题。

AC Code

#include<bits\/stdc++.h>

using namespace std;

const int inf = 0x3f3f3f3f;
const int maxn = 1e4 + 10;

struct note{
	int v,w;
};
vector<note> G[maxn];

int n,m;
int que[maxn];\/\/question 
int s,rt;\/\/存储当前子树大小及重心 
bool ans[maxn];\/\/存储问题答案 

int siz[maxn],f[maxn];\/\/siz子树大小，f最大子树 
int vis[maxn];\/\/表示每个点是否已经被分治过 

\/\/求重心 
void getroot(int u,int fa)
{
	siz[u] = 1;
	f[u] = 0;
	for(auto nxt : G[u])
	{
		int v = nxt.v;
		int w = nxt.w;
		if(vis[v] || v == fa) continue;
		getroot(v,u);
		siz[u] += siz[v];
		f[u] = max(f[u],siz[v]);
	}
	f[u] = max(f[u],s - siz[u]);
	if(f[u] < f[rt]) rt = u;
}

int cnt;
int dis[maxn],d[maxn];

\/\/统计出每个点路径长度 
void getdep(int u,int fa)
{
	dis[++cnt] = d[u];
	for(auto nxt : G[u])
	{
		int v = nxt.v;
		int w = nxt.w;
		if(v == fa || vis[v]) continue;
		d[v] = d[u] + w;
		getdep(v,u);
	}
}

int q[maxn];\/\/队列 存储当前子树内产生贡献的点 
bool judge[10000010];\/\/判断一个数是否存在 

void getans(int u)
{
	judge[0] = 1;
	int p = 0;
	for(auto nxt : G[u])
	{
		int v = nxt.v;
		int w = nxt.w;
		if(vis[v]) continue;
		cnt = 0;
		d[v] = w;
		getdep(v,u);
		for(int i = 1;i <= cnt;i++)
			for(int j = 1;j <= m;j++)
				if(que[j] >= dis[i]) ans[j] |= judge[que[j] - dis[i]];
				
		for(int i = 1;i <= cnt;i++)
		{
			if(dis[i] <= 1e7)
			{
				judge[dis[i]] = 1;
				q[++p] = dis[i];
			}
		}
	}
	for(int i = 1;i <= p;i++) judge[q[i]] = 0;
}

\/\/递归分治
void divide(int u)
{
	vis[u] = 1;\/\/标记当前点 
	getans(u);\/\/统计当前点的答案 
	for(auto nxt : G[u])
	{
		int v = nxt.v;
		int w = nxt.w;
		if(vis[v]) continue;
		s = siz[v];
		f[rt = 0] = inf;
		getroot(v,0);
		divide(rt);
	}
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	for(int i = 1;i < n;i++)
	{
		int u,v,w;
		cin >> u >> v >> w;
		G[u].push_back({v,w});
		G[v].push_back({u,w});
	}
	for(int i = 1;i <= m;i++) cin >> que[i];
	f[rt = 0] = inf; \/\/初始化 
	s = n; \/\/当前子树点的数量 
	getroot(1,0);\/\/找到重心 
	getroot(rt,0);\/\/从重心进行一遍dfs，求出每个点子树大小等信息 
	divide(rt);\/\/分治 
	for(int i = 1;i <= m;i++) \/\/输出答案 
		cout << (ans[i] ? "AYE" : "NAY") << '\n';
	return 0;
}

需要注意的细节：

函数调用不要调用错误。
记得及时清空变量及数组，函数运行前初始化信息。

希望对你有所帮助。

xuyunao 的博客

博客