概念

点分治是一种用于处理大规模树上路径问题的思想。

通常情况下，点分治的时间复杂度是 \(\mathcal{O}(n log n)\) 或 \(\mathcal{O}(n log^2n)\)

点分治和边分治同属树分治。通常情况下，边分治可以解决点分治所能解决的大部分问题。

淀粉质，淀粉汁

思想

P3806 【模板】点分治1

以例题为引。

显然对于一棵有根树，树上的路径可以分成两类：经过根节点的路径和不经过根节点的路径。

实际上，第二种路径可以转化成第一种路径，如下图：

当对以 \(1\) 为根的子树分治时，路径 \(4, 2, 5\) 是不经过根节点的。但是当对以 \(2\) 为根的子树分治时，这条路径经过根节点。

类似地，子树改变时路径的类型也会变化。大规模子树中所有不经过根节点的路径都可以被转化成小规模子树中经过根节点的路径，并且不影响答案。

原因：假设有一树上路径 \(E\)。递归分治某一子树时，若该树上路径中的节点被选为重心，则该路径过重心，被统计。反之，显然这条路径同属于当前分治子树的某一子树。故而递归到下一层时，该路径上的所有节点都会被当前分治的子树包含。由此知经过若干轮递归，该树上路径一定会被统计。又因为该树上路径在树上任取，所以树上的所有路径都会被统计。

从而可以考虑对子树进行分治，借此统计所有的树上路径。

根据题目，分治一棵子树时通常需要对子树进行遍历，单次时间复杂度 \(\mathcal{O}(size)\)。考虑在对子树分治时改变子树结构，使得整棵树平衡。

选取 树的重心 作为子树的根节点即可。

// 选取重心
void get_root(int u, int fa, int tot) {
	size[u] = 1;
	dp[u] = 0;
	for (int i = head[u]; i; i = edge[i].nxt) {
		int v = edge[i].to;
		if ((v == fa) || vis[v]) {
			continue;
		}
		get_root(v, u, tot);
		size[u] += size[v];
		dp[u] = max(dp[u], size[v]);
	}
	dp[u] = max(dp[u], tot - size[u]);
	if ((!root) || (dp[u] < dp[root])) {
		root = u;
	}
}

时间复杂度分析：设树中节点总数为 \(n\)。易知以树的重心为根节点时，根节点的子树大小最大为 \(\frac{n}{2}\)。故而最多递归分治 \(O(log n)\) 层，处理每层的时间复杂度约为 \(\mathcal{O}(n)\) 或 \(\mathcal{O}(n log n)\)。所以总时间复杂度为 \(\mathcal{O}(n log n)\) 或 \(\mathcal{O}(n log^2n)\)。另，一种基于错误的寻找重心方法的点分治的复杂度分析。结论：复杂度不高于一般点分治。

承接上文。当分治以 \(r\) 为根的子树时，需要对子树进行遍历，求取需要的信息。

以例题为例，不妨求出当前分治的子树中所有节点到 \(r\) 的距离，记为 \(dis_u\)。约定在当前子树中，节点 \(u\) 深度为 \(2\)（\(r\) 深度为 \(1\)）的祖先为 \(u\) 所属子树的编号，记为 \(bel_u\)。作为分治的前置信息，遍历一遍子树，记录下经过的节点，依次为 \(pos_1, ..., pos_{len}\)

void get_dis(int u, int fa, int dist, int rt) {
	len++;
	pos[len] = u;
	bel[u] = rt;
	dis[u] = dist;
	for (int i = head[u]; i; i = edge[i].nxt) {
		int v = edge[i].to;
		if ((v == fa) || vis[v]) {
			continue;
		}
		get_dis(v, u, dist + edge[i].w, rt);
	}
}

此时统计答案，注意不同的题目统计答案的方式和位置可能不同。

首先将 \(pos\) 序列按照 \(dis\) 排序。

bool cmp(int a, int b) {
	return dis[a] < dis[b];
}
sort(pos + 1, pos + len + 1, cmp);

已经保证序列有序，因而可以使用 双指针 维护答案。

注意，当存在节点 \(u, v\) 使得 \(dis_u + dis_v = k\) 且 \(u, v\) 同属 \(r\) 的一棵子树时（\(bel_u = bel_v\)），\(u\) 到 \(v\) 的路径不合法（\(u, r\) 之间的路径和 \(v, r\) 之间的路径有重合，长度不为 \(k\)）。

代码实现可以考虑特判或者容斥。

由于例题有多个询问，多次点分治会导致时间复杂度变劣至 \(O(nm log n)\)，因此应该将所有询问离线处理，避免重复计算重心等。

for (int i = 1; i <= m; i++) {
	int l = 1, r = len;
	if (flag[i]) {
		continue;
	}
	while (l < r) {
		if (dis[pos[l]] + dis[pos[r]] > query[i]) {
			r--;
		} else if (dis[pos[l]] + dis[pos[r]] < query[i]) {
			l++;
		} else if (bel[pos[l]] == bel[pos[r]]) {
			if (dis[pos[r]] == dis[pos[r - 1]]) {
				r--;
			} else {
				l++;
			}
		} else {
			flag[i] = true;
			break;
		}
	}
}

分治过程中，树的结构可能发生改变。因此不能通过记录父亲判断是否重复遍历，而应使用 vis 数组。

参考代码中，递归层数 \(\mathcal{O}(log n)\)，处理单层时间复杂度 \(\mathcal{O}(n log n)\)（由于多组询问，自带最大为 \(100\) 的常数），总时间复杂度 \(O(n log^2 n)\)

参考代码

评测记录

代码长度 \(2.42KB\)，总耗时 \(30ms\)，最慢点用时 \(14ms\)，使用空间 \(1.34MB\)

#include 
#include 
using namespace std;

const int maxn = 1e4 + 5;
const int maxm = 2e4 + 5;

struct node {
	int to, nxt, w;
} edge[maxm];

int n, m;
int cnt, len, root;
int query[maxn];
int pos[maxn], bel[maxn], dis[maxn];
int head[maxn], size[maxn], dp[maxn];
bool vis[maxn], flag[maxn];

bool cmp(int a, int b) {
	return dis[a] < dis[b];
}

void add_edge(int u, int v, int w) {
	cnt++;
	edge[cnt].to = v;
	edge[cnt].nxt = head[u];
	edge[cnt].w = w;
	head[u] = cnt;
}

void get_root(int u, int fa, int tot) {
	size[u] = 1;
	dp[u] = 0;
	for (int i = head[u]; i; i = edge[i].nxt) {
		int v = edge[i].to;
		if ((v == fa) || vis[v]) {
			continue;
		}
		get_root(v, u, tot);
		size[u] += size[v];
		dp[u] = max(dp[u], size[v]);
	}
	dp[u] = max(dp[u], tot - size[u]);
	if ((!root) || (dp[u] < dp[root])) {
		root = u;
	}
}

void get_dis(int u, int fa, int dist, int rt) {
	len++;
	pos[len] = u;
	bel[u] = rt;
	dis[u] = dist;
	for (int i = head[u]; i; i = edge[i].nxt) {
		int v = edge[i].to;
		if ((v == fa) || vis[v]) {
			continue;
		}
		get_dis(v, u, dist + edge[i].w, rt);
	}
}

void calc(int u) {
	len = 1;
	pos[len] = u;
	dis[u] = 0;
	bel[u] = u;
	for (int i = head[u]; i; i = edge[i].nxt) {
		int v = edge[i].to;
		if (vis[v]) {
			continue;
		}
		get_dis(v, u, edge[i].w, v);
	}
	sort(pos + 1, pos + len + 1, cmp);
	for (int i = 1; i <= m; i++) {
		int l = 1, r = len;
		if (flag[i]) {
			continue;
		}
		while (l < r) {
			if (dis[pos[l]] + dis[pos[r]] > query[i]) {
				r--;
			} else if (dis[pos[l]] + dis[pos[r]] < query[i]) {
				l++;
			} else if (bel[pos[l]] == bel[pos[r]]) {
				if (dis[pos[r]] == dis[pos[r - 1]]) {
					r--;
				} else {
					l++;
				}
			} else {
				flag[i] = true;
				break;
			}
		}
	}
}

void solve(int u) {
	vis[u] = true;
	calc(u);
	for (int i = head[u]; i; i = edge[i].nxt) {
		int v = edge[i].to;
		if (vis[v]) {
			continue;
		}
		root = 0;
		get_root(v, 0, size[v]);
		solve(root);
	}
}

int main() {
	int u, v, w;
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n - 1; i++) {
		scanf("%d%d%d", &u, &v, &w);
		add_edge(u, v, w);
		add_edge(v, u, w);
	}
	for (int i = 1; i <= m; i++) {
		scanf("%d", &query[i]);
		flag[i] = (!query[i] ? true : false);
	}
	dp[0] = n;
	get_root(1, 0, n);
	solve(root);
	for (int i = 1; i <= m; i++) {
		puts(flag[i] ? "AYE" : "NAY");
	}
	return 0;
}