点分治

发表于 更新于 分类于 ， 阅读次数： 本文字数： 9.3k 阅读时长 ≈ 17 分钟

前言

虽然但是现在才学点分治有点晚了。

算法讲解

概念

处理树上路径问题的一种好算法。

解析

其实不太好解释，来看一道例题。
“求树上距离为 $k$ 的点对是否存在”———— 模板
如果直接暴力查询，那复杂度会很大。
接下来考虑分治：
如果我们随机选取一个点 $P$，只查询跨过这个点的路径，那么就可以不断的递归到子树求解。
弊端：复杂度不太稳定。随机构造一条链，假如每次选择链的端点分治，那么复杂度将达到 $O(n^2)$，不可接受。
那么我们把随机选择一个点改为选择这棵树的重心进行分治，复杂度即可达到稳定的 $O(n\log n)$。
粗浅证明一下：对于树的重心来说，它的任意一棵子树的大小不超过 $\frac{n}{2}$，所以我们只用求 $\log n$ 次重心即可完成分治。

流程

对于 P3806 【模板】点分治 1 来说，首先把 $m$ 个询问离线下来。设当前分治的根为 $root$，接着记录几个数据：

  • 栈 $q$ 记录 $root$ 能到的点（其实就是个数组）
  • 数组 $dis$ 记录点到树根的距离
  • $from$ 记录该点属于 $root$ 的哪一个子树。

接着，将 $q$ 按照 $dis$ 值排序，用双指针遍历数组，排除掉在同一棵子树内的影响，同时记录哪些询问被满足，接着递归至下一层。

Talk is cheap, show me the code.

Code(模板)

例题

P3806 【模板】点分治 1

模板，不多说。

P4178 Tree

https://www.luogu.com.cn/problem/P4178，将模板中的等于 $k$ 改为了小于等于。
同样是用双指针维护，但我们发现。这里不太好处理同一棵子树内部的贡献，于是我们考虑容斥。
由于每棵子树内部的贡献多算了一次，所以直接减掉即可。
具体可看 solve 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
void solve(int u) {
	st[u] = true, ans += calc(u, 0);
	for(int i = h[u]; ~i; i = e[i].ne) {
		int v = e[i].to;
		if(st[v])
			continue;
		root = 0;
		ans -= calc(v, e[i].w);
		get_root(v, u, sz[v]);
		solve(root);
	}
	return ;
}

AC Code

P2634 [国家集训队] 聪聪可可

links。
其实还算简单，具体做法和上一道题差不多，只需要记录点到 $root$ 的距离在模 $3$ 下的同余数即可，计算时因为点对的问题，令 $q_0$ 表示距离余 $0$ 的点的个数，$q_1$ 与 $q_2$ 同理，所以答案应为 $q_0\times q_0+q_1\times q_2\times 2$。

AC Code