点分治 - 题解

标签与难度

标签: 树上问题, DSU on Tree, 树上启发式合并, 动态规划, 深度优先搜索, 二分查找, 树形DP 难度: 2300

题目大意喵~

主人你好呀~！这道题是这样的：我们有一棵由 $n$ 个节点组成的树，需要找到 $k$ 条不重复的路径。我们的目标是，让这 $k$ 条路径的公共交集部分尽可能地长，也就是包含尽可能多的点。最后输出这个最长的交集路径的长度就可以啦，喵~

比如说，路径 $(u, v)$ 和 $(v, u)$ 算作是同一条路径。路径的长度就是它上面点的数量。一个点自己也可以是一条路径，长度为 1。如果找不到满足条件的路径，交集就是空的，长度为 0。

解题思路分析

这道题看起来有点复杂，但别担心，跟着我的思路一步步来，问题就会迎刃而解的，喵！

我们的目标是找到一条路径 $P$ ，使得包含 $P$ 的路径总数不少于 $k$ ，并且 $P$ 的长度要最长。

首先，一个关键的性质是：树上任意多条路径的交集，要么是空，要么还是一条路径。所以我们只需要考虑，哪条路径 $P_{ab}$ (从节点 $a$ 到 $b$ ) 作为交集时，能得到最长的长度。

为了计算包含路径 $P_{ab}$ 的路径数量，我们可以分两种情况来讨论，呐：

情况一： $a$ 是 $b$ 的祖先节点

如果我们的交集路径 $P_{ab}$ 上， $a$ 是 $b$ 的祖先节点（我们先把树随便以一个点，比如 1 号点，为根），那么这条路径的长度是 $\text{depth}[b] - \text{depth}[a] + 1$ 。

什么样的路径会包含 $P_{ab}$ 呢？这样的路径，它的一个端点必须在以 $b$ 为根的子树里，另一个端点必须在以 $a$ 为根的子树的外面。为什么呢？因为只有这样，从一个端点走到另一个端点，才会必然经过从 $a$ 到 $b$ 的这段路。

所以，包含 $P_{ab}$ 的路径数量就是：

\text{count} = \text{size}[b] \times (n - \text{size}[a])

其中 $\text{size}[x]$ 表示以 $x$ 为根的子树大小。我们要找的就是满足 $\text{size}[b] \times (n - \text{size}[a]) \ge k$ 的、有祖孙关系的 $(a, b)$ 对中，使得 $\text{depth}[b] - \text{depth}[a] + 1$ 最大的那一对。

情况二： $a$ 和 $b$ 互不为祖先（"表亲"关系）

如果 $a$ 和 $b$ 没有祖孙关系，设它们的最近公共祖先（LCA）是 $c$ 。那么路径 $P_{ab}$ 就是从 $a$ 先走到 $c$ ，再从 $c$ 走到 $b$ 。

这条路径的长度是 $(\text{depth}[a] - \text{depth}[c]) + (\text{depth}[b] - \text{depth}[c]) + 1$ 。

包含这条路径 $P_{ab}$ 的路径，一个端点必须在以 $a$ 为根的子树里，另一个端点必须在以 $b$ 为根的子树里。这样，路径数量就是：

\text{count} = \text{size}[a] \times \text{size}[b]

我们要找的就是满足 $\text{size}[a] \times \text{size}[b] \ge k$ 的、LCA 为 $c$ 的 $(a, b)$ 对中，使得 $\text{depth}[a] + \text{depth}[b] - 2 \times \text{depth}[c] + 1$ 最大的那一对。

算法的选择：DSU on Tree (树上启发式合并)

直接暴力枚举所有的 $(a, b)$ 对是 $O(N^2)$ 的，肯定会超时的说。我们需要更高效的算法。

对于第二种"表亲"情况，LCA 是一个关键的连接点。这让我们想到了 DSU on Tree！它可以高效地处理子树信息合并的问题。

DSU on Tree 的核心思想是：当一个节点 u 计算完所有子树的信息后，它只保留其重儿子（subtree size 最大的儿子）的子树信息，而轻儿子（其他儿子）的信息则在回溯时清除。对于轻儿子的信息，我们暴力遍历并合并到当前节点 u 的信息中。因为一个节点到根的路径上最多有 $O(\log N)$ 条轻边，所以每个节点的信息最多被暴力合并 $O(\log N)$ 次，总复杂度就很优秀啦！

具体的实现步骤：

预处理 dfs_prepare: 我们先进行一次 DFS，计算出每个节点的 depth（深度）、size（子树大小）、heavy_child（重儿子）以及 max_subtree_depth（子树中的最大深度，用于确定DP数组的边界）。同时，我们可以顺便处理一个最简单的情况：路径长度为 1。如果任意一条边 $(u, v)$ （ $v$ 是 $u$ 的孩子）所能构成的路径数 $\text{size}[v] \times (n - \text{size}[v]) \ge k$ ，那么答案至少是 1。
主过程 dfs_solve (DSU on Tree): 这是我们的核心函数。对于当前节点 u：
- 先递归处理它所有的轻儿子，并且在回溯后清除它们的数据。
- 再递归处理它的重儿子，并保留其数据。
- 现在，我们拥有了 u 的重儿子子树的所有信息。我们用一个数组 max_size_at_depth[d] 来存储，表示在已处理的子树中，深度为 d 的节点的最大 size 是多少。
- 接着，我们暴力遍历 u 的所有轻儿子子树。对于轻儿子子树中的每个节点 x，我们来计算贡献：
  - 表亲情况: x 和重儿子子树中的某个节点 y 构成路径。我们需要找到一个 y，使得 size[x] * size[y] >= k，并且 y 的深度最大。这等价于 size[y] >= ceil(k / size[x])。为了快速找到满足条件的 y，我们可以对 max_size_at_depth 数组做一个小处理，让它变成后缀最大值数组（query_helper[d] = max_size 在深度 d 及更深处），这样就可以用二分查找在 $O(\log N)$ 时间内找到最深的 y 啦！路径长度是 (depth[x] - depth[u]) + (depth[y] - depth[u]) + 1。
- 处理完所有轻儿子与重儿子的组合后，我们将轻儿子的信息也合并到 max_size_at_depth 数组中。
- 祖先-后代情况: u 作为路径的顶端（祖先 a）。我们需要在 u 的整个子树中（现在信息都合并好了）找一个后代 b，使得 size[b] * (n - size[u]) >= k，并且 b 的深度最大。同样，我们可以用二分查找来解决！
- 最后，如果 u 是它父亲的轻儿子，我们就清空为 u 这棵子树计算的所有数据，准备回溯。

通过这个过程，我们就能不重不漏地考虑到所有情况，并找到最长的路径长度啦，喵~

代码实现

cpp

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 200005;
using ll = long long;

int n;
ll k;
vector<int> adj[MAXN];

// 预处理 DFS 需要的数组
int parent[MAXN];
int depth[MAXN];
int subtree_size[MAXN];
int heavy_child[MAXN];
int max_subtree_depth[MAXN];

// DSU on Tree 使用的 DP 数组
int* max_size_at_depth = nullptr; // 指向全局 DP 数组
int current_max_depth; // 当前处理子树的最大深度
int ans;

// 用于二分查找的辅助数组
vector<int> query_helper;

// 预处理 DFS，计算 size, depth, heavy_child 等信息
void dfs_prepare(int u, int p, int d) {
    parent[u] = p;
    depth[u] = d;
    subtree_size[u] = 1;
    heavy_child[u] = -1;
    max_subtree_depth[u] = d;
    int max_sz = 0;

    for (int v : adj[u]) {
        if (v == p) continue;
        dfs_prepare(v, u, d + 1);
        subtree_size[u] += subtree_size[v];
        max_subtree_depth[u] = max(max_subtree_depth[u], max_subtree_depth[v]);
        if (subtree_size[v] > max_sz) {
            max_sz = subtree_size[v];
            heavy_child[u] = v;
        }
        // 顺便检查长度为1的交集（即一条边）
        if ((ll)subtree_size[v] * (n - subtree_size[v]) >= k) {
            ans = max(ans, 1);
        }
    }
}

// 辅助函数，将子树信息更新到 DP 数组
void update_dp(int u) {
    max_size_at_depth[depth[u]] = max(max_size_at_depth[depth[u]], subtree_size[u]);
    current_max_depth = max(current_max_depth, depth[u]);
    for (int v : adj[u]) {
        if (v == parent[u]) continue;
        update_dp(v);
    }
}

// 辅助函数，在子树中查询并更新答案
void query_and_update_ans(int u, int lca) {
    // 情况二：LCA为lca, u和另一支的节点构成路径
    ll required_size = (k + subtree_size[u] - 1) / subtree_size[u];
    if (required_size <= n) {
        // 二分查找满足条件的最深节点
        int l = depth[lca] + 1, r = current_max_depth + 1, best_d = -1;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (query_helper[mid] >= required_size) {
                best_d = mid;
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        if (best_d != -1) {
            ans = max(ans, (depth[u] - depth[lca]) + (best_d - depth[lca]) + 1);
        }
    }

    // 递归处理子节点
    for (int v : adj[u]) {
        if (v == parent[u]) continue;
        query_and_update_ans(v, lca);
    }
}


// DSU on Tree 主函数
void dfs_solve(int u, bool keep_data) {
    // 1. 递归处理轻儿子
    for (int v : adj[u]) {
        if (v != parent[u] && v != heavy_child[u]) {
            dfs_solve(v, false);
        }
    }

    // 2. 递归处理重儿子，并保留数据
    if (heavy_child[u] != -1) {
        dfs_solve(heavy_child[u], true);
    }
    
    // 3. 合并 u 和它的轻儿子子树信息
    max_size_at_depth[depth[u]] = max(max_size_at_depth[depth[u]], subtree_size[u]);
    current_max_depth = max(current_max_depth, depth[u]);

    // 准备用于二分查找的辅助数组
    query_helper.assign(max_subtree_depth[u] + 2, 0);
    for (int i = depth[u]; i <= current_max_depth; ++i) {
        query_helper[i] = max_size_at_depth[i];
    }
    for (int i = current_max_depth - 1; i >= depth[u]; --i) {
        query_helper[i] = max(query_helper[i], query_helper[i+1]);
    }

    // 情况一：u是祖先
    if (u != 1) { // 根节点没有外部节点
        ll required_size = (k + (n - subtree_size[u]) - 1) / (n - subtree_size[u]);
        if (required_size <= n) {
            int l = depth[u] + 1, r = current_max_depth + 1, best_d = -1;
            while (l < r) {
                int mid = l + (r - l) / 2;
                if (query_helper[mid] >= required_size) {
                    best_d = mid;
                    l = mid + 1;
                } else {
                    r = mid;
                }
            }
            if (best_d != -1) {
                ans = max(ans, best_d - depth[u] + 1);
            }
        }
    }

    // 处理轻儿子
    for (int v : adj[u]) {
        if (v != parent[u] && v != heavy_child[u]) {
            query_and_update_ans(v, u); // 查询贡献
            update_dp(v); // 更新DP数组
        }
    }

    // 4. 如果是轻儿子，清除数据
    if (!keep_data) {
        for (int i = depth[u]; i <= max_subtree_depth[u]; ++i) {
            max_size_at_depth[i] = 0;
        }
        current_max_depth = 0;
    }
}

void solve() {
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        adj[i].clear();
    }
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    ans = 0;
    // 如果 k=1，任何一个点都是长度为1的路径，答案至少是1
    if (k == 1) ans = 1;

    dfs_prepare(1, 0, 1);
    
    // 检查单个点作为交集的情况
    for(int i = 1; i <= n; ++i) {
        ll path_count = 1LL * n * (n - 1) / 2;
        ll outside_size = n - subtree_size[i];
        if (outside_size > 1) {
            path_count -= outside_size * (outside_size - 1) / 2;
        }
        for (int v : adj[i]) {
            if (v != parent[i]) {
                if (subtree_size[v] > 1) {
                    path_count -= (ll)subtree_size[v] * (subtree_size[v] - 1) / 2;
                }
            }
        }
        if (path_count >= k) {
            ans = max(ans, 1);
        }
    }


    int* global_dp_buffer = new int[n + 2]();
    max_size_at_depth = global_dp_buffer;
    
    dfs_solve(1, true);
    
    delete[] global_dp_buffer;

    cout << ans << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

复杂度分析

时间复杂度: $O(N \log N)$ 喵~
- dfs_prepare 预处理是 $O(N)$ 的。
- dfs_solve 是 DSU on Tree 的核心。每个节点作为轻儿子的子树的一部分被访问时，其所在子树的大小会减半。因此，每个节点最多在 $O(\log N)$ 条轻边路径上，所以它被作为“需要暴力合并”的节点处理 $O(\log N)$ 次。
- 在 dfs_solve 中，对于每个轻儿子，我们遍历它的子树进行查询和更新。query_and_update_ans 中包含了一个二分查找，但我们是先构建好 query_helper 再统一查询的。更精细的分析是，每个节点被暴力遍历（作为轻子树的一部分）的次数是 $O(\log N)$ 次。因此，总的时间复杂度是 $O(N \log N)$ 。
空间复杂度: $O(N)$ 的说。
- 邻接表 adj 存储树的结构，需要 $O(N)$ 空间。
- 各种预处理数组如 depth, size 等都是 $O(N)$ 的。
- 全局的 DP 数组 max_size_at_depth 和辅助的 query_helper 也是 $O(N)$ 的。
- 递归栈的深度最多是 $O(N)$ 。

知识点总结

这道题是一道非常好的树上问题练习题，融合了多种思想，喵~

问题转化: 把一个模糊的“最长交集”问题，转化为具体的、可计算的两种情况（祖先-后代，表亲），这是解题的第一步！
DSU on Tree (树上启发式合并): 这是解决一类树上子树统计问题的强力模板。核心是利用树的重链剖分思想，保留重儿子的信息，只暴力合并轻儿子的信息，从而优化复杂度。
树形DP: 本质上，max_size_at_depth 数组就是一种DP状态的记录。我们自底向上地合并子树信息，计算出当前子树的答案。
二分查找: 当我们需要在一个满足单调性的序列中查找某个边界时，二分查找是绝佳的工具。这里我们通过构建后缀最大值数组，创造了单调性，从而可以将 $O(N)$ 的查询优化到 $O(\log N)$ 。

希望这篇题解能帮助到你，如果还有不明白的地方，随时可以再来问我哦！一起加油，喵~！

点分治 - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

情况一：aaa 是 bbb 的祖先节点 ​

情况二：aaa 和 bbb 互不为祖先（"表亲"关系） ​

算法的选择：DSU on Tree (树上启发式合并) ​

具体的实现步骤： ​

代码实现 ​

复杂度分析 ​

知识点总结 ​