树的直径与重心：核心算法与实现

核心逻辑与数学原理

树的直径与重心是描述树形拓扑结构非对称性的两个核心度量指标。

1. 树的直径 (Diameter)

树的直径定义为树中所有路径长度的最大值，即 $\max_{u, v \in V} \text{dist}(u, v)$。

• 两次 DFS 法的数学原理：
  从任意节点 $x$ 出发进行第一次 DFS，到达的最远节点必然是某条直径的一个端点 $u$。再从 $u$ 出发进行第二次 DFS，到达的最远节点必然是该直径的另一个端点 $v$。
  证明梗概： 设存在一条直径 $(p, q)$。从 $x$ 到达的最远点为 $u$。若 $u$ 不在直径上，则路径 $\text{dist}(x, u) \ge \text{dist}(x, p)$。结合树的无环连通性，必然能构造出一条比 $(p, q)$ 更长的路径，与 $(p, q)$ 是直径矛盾。
  局限性： 只能处理边权非负的树。若存在负边权，该贪心证明失效。
• 树形 DP 法的数学原理：
  任选一点为根。对于任意节点 $u$，经过 $u$ 的最长路径由 $u$ 子树内的最长链与次长链拼接而成。该方法天然支持负边权。

2. 树的重心 (Centroid)

树的重心定义为一个节点 $u$，当把 $u$ 拆除后，分裂出的所有连通块（子树）中，节点数最多的连通块的大小达到最小。

• 数学性质：

1. 树的重心最多有两个。若有两个重心，它们必然由一条边直接相连，且此时分裂出的最大子树大小严格等于 $\frac{N}{2}$。
2. 节点 $u$ 是重心的充要条件：以 $u$ 为根时，其所有子节点 $v$ 的子树大小 $\text{siz}[v] \le \frac{N}{2}$，且 $N - \text{siz}[u] \le \frac{N}{2}$。
3. 树中所有点到重心的距离之和最小。

状态设计与算法推导

1. 树形 DP 求直径

定义 $d_1[u]$ 为以 $u$ 为根的子树中，$u$ 到叶子节点的最长路径长度；$d_2[u]$ 为次长路径长度。
全局直径记为 $\text{ans}$。
对于任意子节点 $v \in \text{adj}[u]$，边权为 $w$：

1. 状态转移方程：
   在更新 $d_1[u]$ 之前，先尝试拼接触发全局最大值：

$$\text{ans} = \max(\text{ans}, d_1[u] + d_2[v] + w)$$

2. 维护最长链与次长链：
   若 $d_1[v] + w > d_1[u]$，则 $d_2[u] = d_1[u]$, $d_1[u] = d_1[v] + w$。
   否则，若 $d_1[v] + w > d_2[u]$，则 $d_2[u] = d_1[v] + w$。

2. 树的重心推导

定义 $\text{siz}[u]$ 为以 $u$ 为根的子树大小，$\text{max\_part}[u]$ 为删除 $u$ 后产生的最大连通块大小。
对于任意子节点 $v \in \text{adj}[u]$：

1. 后序遍历回溯时累加：$\text{siz}[u] = 1 + \sum \text{siz}[v]$
2. 局部子树最大值：$\text{max\_part}[u] = \max_{v \in \text{adj}[u]} (\text{siz}[v])$
3. 考虑非子树方向的父节点连通块：

$$\text{max\_part}[u] = \max(\text{max\_part}[u], N - \text{siz}[u])$$

4. 重心满足：$\text{max\_part}[\text{centroid}] = \min_{i \in V}(\text{max\_part}[i])$

C++ 标准源码

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

const int MAXN = 200005;

struct Edge {
    int to;
    long long weight;
};

std::vector<Edge> adj[MAXN];
int n;

// 直径相关变量
long long max_dia = 0;
long long d1[MAXN], d2[MAXN];

// 重心相关变量
int siz[MAXN];
int max_part[MAXN];
std::vector<int> centroids;

// 树形 DP 求直径（支持负边权）
void dfs_diameter(int u, int fa) {
    d1[u] = 0;
    d2[u] = 0;
    for (size_t i = 0; i < adj[u].size(); ++i) {
        int v = adj[u][i].to;
        long long w = adj[u][i].weight;
        if (v == fa) continue;

        dfs_diameter(v, u);

        // 核心踩坑点：必须在更新 d1[u] 之前更新全局直径，防止同一子树的最长链被重复计算
        if (d1[v] + w > d1[u]) {
            d2[u] = d1[u];
            d1[u] = d1[v] + w;
        } else if (d1[v] + w > d2[u]) {
            d2[u] = d1[v] + w;
        }
    }
    max_dia = std::max(max_dia, d1[u] + d2[u]);
}

// DFS 求重心
void dfs_centroid(int u, int fa) {
    siz[u] = 1;
    max_part[u] = 0;

    for (size_t i = 0; i < adj[u].size(); ++i) {
        int v = adj[u][i].to;
        if (v == fa) continue;

        dfs_centroid(v, u);
        siz[u] += siz[v];
        max_part[u] = std::max(max_part[u], siz[v]);
    }

    // 考虑上方父节点方向的连通块大小
    max_part[u] = std::max(max_part[u], n - siz[u]);

    // 判定是否为重心
    if (max_part[u] <= n / 2) {
        centroids.push_back(u);
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    if (!(std::cin >> n)) return 0;

    for (int i = 1; i < n; ++i) {
        int u, v;
        long long w;
        std::cin >> u >> v >> w;
        adj[u].push_back(Edge{v, w});
        adj[v].push_back(Edge{u, w});
    }

    // 计算直径
    dfs_diameter(1, 0);

    // 计算重心
    dfs_centroid(1, 0);

    std::cout << "Diameter: " << max_dia << "\n";
    std::cout << "Centroid(s): ";
    for (size_t i = 0; i < centroids.size(); ++i) {
        std::cout << centroids[i] << " ";
    }
    std::cout << "\n";

    return 0;
}

NOIP 实战避坑指南

1. 两次 DFS 法求直径处理负权边死循环/逻辑错误：
   若树中包含负权边，第一次 DFS 找到的最远点可能根本不是直径端点。此时必须使用树形 DP 求解。另外，计算最长与次长链时，若不小心把一根链的数据同时赋给了 $d_1$ 和 $d_2$，会导致一条边被重复计算两次。
2. 重心判定条件漏写 n - siz[u]：
   很多选手只关注了子节点方向的子树大小（即 max_part[u] = max(max_part[u], siz[v])），完全忽略了向根节点方向回溯时，由非自身子树组成的那部分连通块。若漏掉 max_part[u] = max(max_part[u], n - siz[u])，在处理链状树或根节点单侧极度倾斜的树时，求出的重心必然错误。

经典 NOIP/洛谷 真题

1. 洛谷 P1099 [NOIP2007 提高组] 树网的核

• 题意描述：
  在一棵给定的带权树中，定义一条路径的“偏离度”为树中所有点到该路径距离的最大值。现要在树的直径上选择一条长度不超过 $s$ 的路径（可以是一个点），使得该路径的偏离度最小。求这个最小偏离度。
• 问题本质与核心思路：
  问题的物理核心建立在树的直径性质上。首先用双指针或 DFS 提取出任意一条直径。可以证明，所有直径上的点的偏离度计算，其最大距离点必然通过不经过直径其他点的子树延伸出去。通过直径上的树形 DP 预处理出每个点不沿直径方向的最远距离。接着利用单调队列或双指针在直径序列上维护一个长度不超过 $s$ 的滑动窗口，快速检索区间内外的最大偏离值，复杂度控制在 $O(N)$。

2. 洛谷 P1395 会议

• 题意描述：
  有一个村庄，村庄里的房屋结构形成一棵树。现在要建一个会议中心，使得所有居民点到会议中心的距离之和最小。如果存在多个这样的地点，输出编号最小的那个，并输出最小距离和。
• 问题本质与核心思路：
  树的重心的经典应用。根据重心的性质 3：树中所有点到某个点的距离之和最小的点就是树的重心。因此，第一步通过一轮 DFS 求出树的重心（若有两个重心，取编号小的那个）。第二步以选定的重心为根，再跑一次 DFS，累加所有节点的深度即为各点到重心的距离之和。总时间复杂度为标准的 $O(N)$。