C++树分治算法详解（从零开始掌握树的重心分解与分治思想）

第一步：找树的重心

要实现树分治，首先要能快速找到任意子树的重心。重心的定义是：删除该点后，最大连通块的节点数最小。

我们通过一次 DFS 计算子树大小，再根据定义判断重心：

// 全局变量声明const int MAXN = 10005;vector<int> graph[MAXN];bool visited[MAXN];int subtree_size[MAXN];int total_nodes;void dfs_size(int u, int parent) {    subtree_size[u] = 1;    for (int v : graph[u]) {        if (v != parent && !visited[v]) {            dfs_size(v, u);            subtree_size[u] += subtree_size[v];        }    }}int find_centroid(int u, int parent) {    for (int v : graph[u]) {        if (v != parent && !visited[v] && subtree_size[v] > total_nodes / 2) {            return find_centroid(v, u);        }    }    return u;}

第二步：实现树分治主框架

有了重心查找函数，我们就可以构建分治主函数。通常我们会写一个 solve(int root) 函数，它完成以下步骤：

1. 计算以 root 为根的子树大小；
2. 找到该子树的重心；
3. 标记重心为已访问；
4. 处理所有经过重心的路径（这是具体问题的核心逻辑）；
5. 对重心的每个未访问子树递归调用 solve。

void decompose(int root) {    // 1. 计算子树大小    dfs_size(root, -1);    total_nodes = subtree_size[root];    // 2. 找到重心    int centroid = find_centroid(root, -1);    // 3. 标记重心    visited[centroid] = true;    // 4. 处理经过 centroid 的路径（示例：统计距离为 k 的点对）    process_paths(centroid);    // 5. 递归处理子树    for (int v : graph[centroid]) {        if (!visited[v]) {            decompose(v);        }    }}

第三步：具体问题应用——统计距离为 K 的点对

假设题目要求：给定一棵无根树，每条边权为1，问有多少对点 (u, v) 满足 dist(u, v) == K。

我们可以利用树分治，在每次处理重心时，收集所有子树中各点到重心的距离，然后组合不同子树中的点对，避免重复计数。

const int MAXK = 10005;int count_dist[MAXK];int ans = 0;void dfs_dist(int u, int parent, int d, vector<int>& distances) {    if (d > K) return;    distances.push_back(d);    for (int v : graph[u]) {        if (v != parent && !visited[v]) {            dfs_dist(v, u, d + 1, distances);        }    }}void process_paths(int centroid) {    memset(count_dist, 0, sizeof(count_dist));    count_dist[0] = 1; // 重心自身    for (int v : graph[centroid]) {        if (visited[v]) continue;        vector<int> distances;        dfs_dist(v, centroid, 1, distances);        // 先统计答案（避免同一子树内配对）        for (int d : distances) {            if (d <= K) {                ans += count_dist[K - d];            }        }        // 再合并到全局计数        for (int d : distances) {            if (d <= K) {                count_dist[d]++;            }        }    }}

总结

通过以上步骤，我们完成了基于C++算法实现的树分治模板。关键点在于：

• 正确找到重心以保证复杂度；
• 在 process_paths 中避免同一子树内的错误配对；
• 合理使用 visited 数组防止重复访问。

树分治虽然初看复杂，但一旦掌握其“分而治之”的思想，就能高效解决许多树上路径类难题。建议读者动手实现上述代码，并尝试修改以适应不同题目（如带权边、求最远点对等）。

希望这篇C++树分治教程能帮助你打开高级图论算法的大门！