点分治

点分治是个好东西。

P3806 【模板】点分治 1

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

首先把询问离线。在之后的过程里一起统计答案。

树上距离 \(k\) 的点对，可以完全对应一条长度为 \(k\) 的路径。点分治就是处理这样一轮有关树上路径的问题。

不妨随便在树中选择一个点，然后分类讨论这条路径是否经过这个点。或者说，随便选一个点 \(root\) 作为树的根（这棵树原本是无根树），然后讨论路径是否经过根。这里到底选择哪个点作为树根后面再提。

如果这条路径不经过 \(root\)，换言之这条路径的端点的 LCA 不为 \(root\)。那么将 \(root\) 删掉后，可以对于每个独立的连通块分别递归求解。或者说递归处理 \(root\) 的所有子树。

所以我们只需要求解第二种情况，即这条路径经过 \(root\)。

此时这条路径的两个端点会有两种情况：

• 一个端点为 \(root\)；
• 两个端点都不为 \(root\)。

（还有一种两个端点都为 \(root\) 的情况太过简单。）

不难发现，后一种路径是由两条前一种路径构成的。例如 \(root \to A \to B\) 和 \(root \to C \to D\) 可以拼成 \(B \to A \to root \to C \to D\)。

但是，\(root \to A \to B\) 和 \(root \to A \to C\) 并无法组成一条合法的第二种路径。也就是说我们选择路径端点时，需要强制它们不在同一棵 \(root\) 的儿子的子树内。

如何做到这个强制？很简单。我们按照顺序枚举 \(root\) 的儿子，然后枚举这个儿子的子树内的所有点，先尝试更新答案，再修改维护的数据结构（总结就是 先查询后修改）。例如：

void work(int u, int F) {
    // 查询
    {}
    for (int v : g[u])
        if (!vis[v] && v != F) {
            work(v, u);
        }
    // 修改
    {}  
}

void dfs(int u) {
    vis[u] = true;
    for (int v : g[u])
        if (!vis[v]) {
            work(v);
        }
  	// 清空
    {}
    for (int v : g[u])
        if (!vis[v]) {
            dfs(v);
        }
}

于是分别实现 // 查询 {}、// 修改 {}、// 清空 {} 就好了。

对于本题，我们只需要维护一个 bool 数组 \(f(i)\)，表示是否出现过一个点距离 \(root\) 为 \(i\)。

那么查询和修改就只需要这样写：

res |= f[k - dis[u]];

f[dis[u]] = true;

\(dis(i)\) 表示点 \(i\) 到 \(u\) 的距离。这个是好维护的。

清空时直接 memset 复杂度不对。我们需要再进行类似上面的 work 函数。

void work(int u, int F) {
    f[dis[u]] = false;
    for (int v : g[u])
        if (!vis[v] && v != F) {
            work(v, u);
        }
}

至此，这个算法看起来很对。但是我们每访问到一个点，就去遍历它的所有子树，这样做复杂度实际上是 \(\mathcal O(n^2)\) 的（\(\sum_u size(u) = \mathcal O(n^2\))）。

如何优化？我们思考到底哪个点作为根 \(root\) 最优。

树的中心有性质：它的每个儿子的子树的大小 \(\le\) 总点数的一半。

如果选择树的中心作为根节点，那么最多递归 \(\log n\) 次，树的大小就会变成 \(0\)。（可以类比一下，如果树是一条链，那么与二分的过程很像。）

于是复杂度降至 \(\mathcal O(n \log n)\)。