树的直径 (Tree Diameter)¶

树的直径（Tree Diameter）是无向无环图（树）中最基础也是最重要的拓扑度量之一，指的是树中任意两点之间简单路径长度（权值和）的最大值。连接该最长路径的两个端点，称为直径端点；该最长路径本身亦常被称为树的直径。

树的直径不仅在网络路由、分布式系统拓扑分析、最长关键路径规划等工业场景中扮演核心角色，也是算法竞赛（Codeforces, AtCoder, IOI/NOIP）及高频算法面试中的经典核心考点。

1. 核心定义与拓扑性质¶

1.1 基础定义¶

设 $T = (V, E)$ 为一棵含有 $n$ 个节点的无向无环树，边 $e = (u, v) \in E$ 具有权值 $w(e)$（若为无权树，则默认边权为 $1$）。

路径距离：对任意两点 $u, v \in V$，记 $\text{dist}(u, v)$ 为 $u$ 与 $v$ 之间唯一的简单路径上所有边权之和。
树的直径： $$D(T) = \max_{u, v \in V} \text{dist}(u, v)$$
偏心距 (Eccentricity)：任意节点 $u$ 到树中其他节点的最大距离，记作： $$\epsilon(u) = \max_{v \in V} \text{dist}(u, v)$$
树的半径 (Radius) 与 树的中心 (Center)：
树的半径为所有节点偏心距的最小值：$R(T) = \min_{u \in V} \epsilon(u)$；
使得偏心距取得最小值的节点 $c$ 称为树的中心点 (Center)。

1.2 核心拓扑定理¶

[!NOTE] 引理 1（最远点引理 / 端点贪心引理） 在所有边权均为非负数（$w(e) \ge 0$）的树中，从树上任意选定一个节点 $u \in V$ 出发，所能到达的距离 $u$ 最远的节点 $p$（即满足 $\text{dist}(u, p) = \epsilon(u)$），必定是树的某条直径的一个端点。

[!NOTE] 定理 1（若尔当树中心定理 / Jordan, 1869） 任何树的所有直径路径必定相交于同一个公共部分。树的中心节点至多有 1 个（若直径边数为偶数，中心为单个节点）或 2 个（若直径边数为奇数，中心为一条边的两个相邻端点）。树的中心恰好位于任何一条直径的中点上，且树的半径与直径满足： $$R(T) = \left\lceil \frac{D(T)}{2} \right\rceil$$

[!NOTE] 定理 2（两树合并新直径定理） 设树 $T_1$ 的一条直径端点为 $\{u_1, v_1\}$，树 $T_2$ 的一条直径端点为 $\{u_2, v_2\}$。若添加一条权重为 $w$ 的无向边将 $T_1$ 的某个节点与 $T_2$ 的某个节点相连形成新树 $T'$，则新树 $T'$ 的直径端点必定完全落在集合 $\{u_1, v_1, u_2, v_2\}$ 中。

2. 算法一：两次 DFS / BFS 算法与严格数学证明¶

2.1 算法流程¶

两次搜索法是求解无负权边树直径最直观、常数最小的算法，时间复杂度严格为 $\mathcal{O}(V + E) = \mathcal{O}(n)$：

第一遍搜索：从树中任取一个节点 $x$ 出发，运行一次 BFS 或 DFS，找到距离 $x$ 最远的节点，记为 $p$；
第二遍搜索：从节点 $p$ 出发，运行第二次 BFS 或 DFS，找到距离 $p$ 最远的节点，记为 $q$；
输出结果：$p$ 和 $q$ 即为树的一对直径端点，路径 $p \leadsto q$ 的长度 $\text{dist}(p, q)$ 即为树的直径 $D(T)$。在搜索过程中记录每个节点的前驱指针，即可 $\mathcal{O}(n)$ 还原整条直径上的节点序列。

graph LR
    X((任意起点 x)) -->|第一次 BFS/DFS| P((最远点 p\n直径端点 A))
    P -->|第二次 BFS/DFS| Q((最远点 q\n直径端点 B))
    P -.->|树的直径路径 dist(p, q)| Q

2.2 严格数学证明（反证法）¶

许多初学者容易对“为什么从任意点出发找到的最远点 $p$ 一定是直径端点”感到困惑。下面给出严谨的数学证明。

证明目标¶

设树中某条真实直径为路径 $AB$，其长度为 $D = \text{dist}(A, B)$。任选起点 $u$，令 $p$ 满足 $\text{dist}(u, p) = \max_{x} \text{dist}(u, x)$。求证：存在一条树的直径以 $p$ 为其中一个端点。

分类讨论¶

树中任意两点间的简单路径是唯一的。根据路径 $u \leadsto p$ 与已存在的某条直径 $A \leadsto B$ 是否有公共交点，分为两种情况：

情况 1：路径 $u \leadsto p$ 与直径 $A \leadsto B$ 有公共相交节点¶

设两路径相交的节点中离 $p$ 最近的交点为 $C$（由于树无环，交集必然是一条连续路径或单个节点，设 $C$ 属于该交集）。

根据路径分解： $$\text{dist}(u, p) = \text{dist}(u, C) + \text{dist}(C, p)$$
因为 $A$ 是树中节点，所以从 $u$ 到 $A$ 的距离为： $$\text{dist}(u, A) = \text{dist}(u, C) + \text{dist}(C, A)$$
由 $p$ 的定义知 $p$ 是距离 $u$ 的全局最远点，故： $$\text{dist}(u, p) \ge \text{dist}(u, A)$$ $$\text{dist}(u, C) + \text{dist}(C, p) \ge \text{dist}(u, C) + \text{dist}(C, A)$$
两侧消去非负项 $\text{dist}(u, C)$，得到重要不等式： $$\text{dist}(C, p) \ge \text{dist}(C, A)$$
现考察从直径另一端点 $B$ 经由 $C$ 走到 $p$ 的路径 $B \leadsto C \leadsto p$： $$\text{dist}(B, p) = \text{dist}(B, C) + \text{dist}(C, p) \ge \text{dist}(B, C) + \text{dist}(C, A) = \text{dist}(A, B) = D$$
但已知 $D$ 是全树最长简单路径的距离上限，因此必然有 $\text{dist}(B, p) \le D$。
结合上述两式，必有 $\text{dist}(B, p) = D$！
结论：路径 $B \leadsto p$ 的长度恰好等于树的直径 $D$，即 $p$ 是树的一条合法直径端点。证毕。

情况 2：路径 $u \leadsto p$ 与直径 $A \leadsto B$ 无公共相交节点¶

由于树是连通无环图，路径 $u \leadsto p$ 与直径 $A \leadsto B$ 之间必然存在唯一的一条无环连接链。设该连接链在 $u \leadsto p$ 上的接入点为 $X$，在直径 $A \leadsto B$ 上的接入点为 $C$（其中 $X \neq C$，连接链长度 $\text{dist}(X, C) > 0$）。

此时从 $u$ 到 $A$ 的路径必须经过 $X$ 和 $C$： $$\text{dist}(u, A) = \text{dist}(u, X) + \text{dist}(X, C) + \text{dist}(C, A)$$
从 $u$ 到 $p$ 的路径经过 $X$： $$\text{dist}(u, p) = \text{dist}(u, X) + \text{dist}(X, p)$$
由 $p$ 是距 $u$ 的最远点性质： $$\text{dist}(u, p) \ge \text{dist}(u, A)$$ $$\text{dist}(u, X) + \text{dist}(X, p) \ge \text{dist}(u, X) + \text{dist}(X, C) + \text{dist}(C, A)$$
消去 $\text{dist}(u, X)$： $$\text{dist}(X, p) \ge \text{dist}(X, C) + \text{dist}(C, A)$$
两侧同时加上非负距离 $\text{dist}(X, C)$： $$\text{dist}(C, p) = \text{dist}(C, X) + \text{dist}(X, p) \ge 2 \cdot \text{dist}(X, C) + \text{dist}(C, A) > \text{dist}(C, A)$$
于是考察路径 $B \leadsto C \leadsto X \leadsto p$ 的总长： $$\text{dist}(B, p) = \text{dist}(B, C) + \text{dist}(C, p) > \text{dist}(B, C) + \text{dist}(C, A) = D$$
这推导出了 $\text{dist}(B, p) > D$，与 $D$ 是全树的最大距离相矛盾！
因此在非负权树中，情况 2 实际上不可能出现。综合情况 1 与情况 2，命题得证。

[!WARNING] 负权边反例与适用边界 上述证明中，消去不等式公共项高度依赖所有边权非负的先决条件。若树中存在负权边，$p$ 可能只是因为经过了某条负权抵消路径而不再是直径端点。因此： - 两次 DFS/BFS 法：仅适用于非负边权树； - 带负权边或带点权树：必须使用树形 DP 求解。

3. 算法二：树形动态规划（Tree DP）算法¶

树形 DP 是求解树的直径最普适的方法，它不仅支持负权边，还能轻松拓展到节点带权（点权）、子树约束等各种复杂变种中。

3.1 核心状态设计¶

在树中，任意一条简单路径都可以唯一地被其最高转折点（即该路径两个端点的最近公共祖先 LCA）所标识。

任选树中一个节点作为根节点（例如节点 $1$ 或 $0$），后序遍历整棵树：

设 $d_1[u]$ 表示以节点 $u$ 为根的子树中，$u$ 向下延伸到叶子节点的最大深度（最长链长度）；
设 $d_2[u]$ 表示以节点 $u$ 为根的子树中，$u$ 向下延伸且与最长链不属于同一子树分支的次大深度（次长链长度）；
对于当前节点 $u$，穿过 $u$ 且以 $u$ 为最高顶点的最长简单路径长度显然等于： $$L(u) = d_1[u] + d_2[u]$$
全树的直径即为遍历所有节点作为最高转折点时的最大值： $$D(T) = \max_{u \in V} (d_1[u] + d_2[u])$$

graph TD
    U((转折点 u)) -->|最长链 d1[u]| V1((子树分支 1 ... 最深叶子))
    U -->|次长链 d2[u]| V2((子树分支 2 ... 次深叶子))
    style U fill:#f96,stroke:#333,stroke-width:2px

3.2 状态转移方程¶

在 DFS 遍历 $u$ 的每一个子节点 $v$（边权为 $w$）时，动态更新最大值与次大值：

设当前子节点贡献的链长为 $cur = d_1[v] + w$：

先用已有的 $d_1[u]$ 与新来的 $cur$ 更新全局直径： $$\text{diameter} = \max(\text{diameter}, d_1[u] + cur)$$
若 $cur > d_1[u]$： $$d_2[u] = d_1[u], \quad d_1[u] = cur$$
否则若 $cur > d_2[u]$： $$d_2[u] = cur$$

void dfs(int u, int p) {
    d1[u] = 0;
    d2[u] = 0;
    for (const auto &[v, w] : adj[u]) {
        if (v == p) continue;
        dfs(v, u);
        int cur = d1[v] + w;
        if (cur > d1[u]) {
            d2[u] = d1[u];
            d1[u] = cur;
        } else if (cur > d2[u]) {
            d2[u] = cur;
        }
    }
    max_diameter = std::max(max_diameter, d1[u] + d2[u]);
}

3.3 两种解法综合对比¶

算法指标	两次 DFS / BFS 算法	树形动态规划 (Tree DP)
时间复杂度	$\mathcal{O}(V + E)$（精确访问 $2n$ 次）	$\mathcal{O}(V + E)$（精确访问 $n$ 次）
空间复杂度	$\mathcal{O}(n)$	$\mathcal{O}(n)$（调用栈开销）
边权支持范围	仅限非负权边（$w \ge 0$）	支持任意实数边权（含负权）
点权支持能力	较繁琐（需转换边权）	极度天然支持（如 LC 124）
还原直径路径	极其容易（直接前驱回溯）	较繁琐（需额外记录转移来源）
树的中心提取	极度便捷（直接取路径中点）	需结合换根 DP 才能方便得到

4. 进阶拓扑性质与拓展应用¶

4.1 树的中心 (Tree Center) 与最小高度树¶

在无向图中，若我们希望选定一个节点作为树的根节点，使得整棵树的“最大高度”（即根节点的偏心距 $\epsilon(\text{root})$）最小，这个最优的根节点即为树的中心。

求解树中心的两种方法¶

方法一：直径中点法（基于两次 BFS）：
运行两次 BFS 求出一条直径序列 $path = [p, v_1, v_2, \dots, q]$，总边数为 $D$；
若 $D$ 为偶数，中心节点为 $path[D / 2]$（唯一）；
若 $D$ 为奇数，中心节点为 $path[\lfloor D / 2 \rfloor]$ 和 $path[\lceil D / 2 \rceil]$（共 2 个）。
方法二：拓扑剥洋葱法（类似 Kahn 算法）：
将所有度数为 $1$ 的叶子节点推入队列；
逐层向内剥除叶子，并将邻接点度数减 $1$；
重复剪枝，直到最后剩余 $1$ 个或 $2$ 个节点，该剩余节点即为树的中心（LeetCode 310 标准解法）。

4.2 两棵树合并后的新直径定理¶

在题目 LeetCode 3203 - 合并两棵树后的最小直径中：

给定两棵相互独立的树 $T_1$ 和 $T_2$，各自的直径分别为 $D_1$ 和 $D_2$。我们可以在 $T_1$ 中选定一个节点 $u$，在 $T_2$ 中选定一个节点 $v$，并在 $u$ 和 $v$ 之间添加一条权值为 $1$ 的边将两棵树联结成一棵大树 $T'$。如何选点才能使得 $T'$ 的直径最小？

定理推导与最优策略¶

添加边 $(u, v)$ 后，新树 $T'$ 中的最长路径只有三种可能来源：

完全位于树 $T_1$ 内部：最大长度为 $D_1$；
完全位于树 $T_2$ 内部：最大长度为 $D_2$；
跨越两棵树：最长路径经过跨树边 $(u, v)$，长度为 $\epsilon_{T_1}(u) + 1 + \epsilon_{T_2}(v)$。

为了最小化跨树路径，我们必须使 $\epsilon_{T_1}(u)$ 和 $\epsilon_{T_2}(v)$ 同时达到各自树内的最小值。根据若尔当定理：

偏心距最小的节点即为树的中心节点，其最小偏心距为树的半径 $R(T) = \lceil D / 2 \rceil$。

因此，最优策略是将两棵树的中心节点连接，合并后新树的最小直径为： $$D_{\min}(T') = \max\left(D_1, \; D_2, \; \left\lceil \frac{D_1}{2} \right\rceil + \left\lceil \frac{D_2}{2} \right\rceil + 1\right)$$

5. 现代 C++ 规范实现模板¶

下面给出封装完整的 TreeDiameter 模板，同时支持带权边、求直径长度、提取整条直径路径与提取树的中心节点。

#include <vector>
#include <algorithm>
#include <queue>

struct TreeDiameter {
    int n;
    struct Edge {
        int to;
        long long weight;
    };
    std::vector<std::vector<Edge>> adj;

    explicit TreeDiameter(int n) : n(n), adj(n + 1) {}

    void add_edge(int u, int v, long long w = 1) {
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    // 运行单源 BFS，返回 (最远点, 距离数组, 前驱父节点数组)
    struct BFSResult {
        int farthest_node;
        std::vector<long long> dist;
        std::vector<int> parent;
    };

    BFSResult bfs(int start_node) const {
        std::vector<long long> dist(n + 1, -1);
        std::vector<int> parent(n + 1, 0);
        std::queue<int> q;

        dist[start_node] = 0;
        q.push(start_node);

        int farthest_node = start_node;
        long long max_d = 0;

        while (!q.empty()) {
            int u = q.front();
            q.pop();

            if (dist[u] > max_d) {
                max_d = dist[u];
                farthest_node = u;
            }

            for (const auto &edge : adj[u]) {
                if (dist[edge.to] == -1) {
                    dist[edge.to] = dist[u] + edge.weight;
                    parent[edge.to] = u;
                    q.push(edge.to);
                }
            }
        }
        return {farthest_node, dist, parent};
    }

    // 求解直径，返回结构包含：长度、端点 u 与 v、直径完整路径节点
    struct DiameterResult {
        long long diameter;
        int u;
        int v;
        std::vector<int> path;
        std::vector<int> centers; // 树的中心节点 (1 或 2 个)
    };

    DiameterResult get_diameter() const {
        // 第一次搜索：从任意点 1 找到最远点 u
        BFSResult r1 = bfs(1);
        int u = r1.farthest_node;

        // 第二次搜索：从点 u 找到最远点 v
        BFSResult r2 = bfs(u);
        int v = r2.farthest_node;
        long long max_diameter = r2.dist[v];

        // 回溯还原路径：从 v 沿着 parent 指针反推至 u
        std::vector<int> path;
        int curr = v;
        while (curr != 0) {
            path.push_back(curr);
            if (curr == u) break;
            curr = r2.parent[curr];
        }
        std::reverse(path.begin(), path.end());

        // 计算中心点 (无权边意义下等分节点数量)
        std::vector<int> centers;
        int k = path.size();
        if (k % 2 == 1) {
            centers.push_back(path[k / 2]);
        } else {
            centers.push_back(path[k / 2 - 1]);
            centers.push_back(path[k / 2]);
        }

        return {max_diameter, u, v, path, centers};
    }
};

6. 精选 LeetCode 经典真题与解题提示¶

以下精选了 7 道覆盖二叉树、带负权点权、多叉树、拓扑剥叶、树合并及子树枚举的代表性真题：

1. LeetCode 543 - 二叉树的直径 (Diameter of Binary Tree) `简单`¶

题意简述：给定一棵二叉树，求任意两个节点之间最长路径的长度（以边数衡量）。
算法核心：
二叉树树形 DP 经典入门题；
后序遍历递归函数 maxDepth(node) 计算并返回当前节点向下的单侧最大深度；
递归回溯时，用左子树深度与右子树深度之和 left + right 更新全局直径变量；
向上返回当前节点的最大单侧深度 max(left, right) + 1。

查看解题核心代码

class Solution {
    int max_diameter = 0;
    int maxDepth(TreeNode* root) {
        if (!root) return 0;
        int left = maxDepth(root->left);
        int right = maxDepth(root->right);
        max_diameter = std::max(max_diameter, left + right);
        return std::max(left, right) + 1;
    }
public:
    int diameterOfBinaryTree(TreeNode* root) {
        maxDepth(root);
        return max_diameter;
    }
};

2. LeetCode 124 - 二叉树中的最大路径和 (Binary Tree Maximum Path Sum) `困难`¶

题意简述：路径被定义为一条从树中任意节点出发，沿父子相连到达任意节点的序列。序列中至少包含一个节点，求路径中节点值的最大总和（节点权值可能为负数）。
算法核心：
典型的带负权点权的树的直径问题，两次 BFS 贪心失效，必须使用树形 DP；
递归函数计算每个子树能为父节点提供的单侧最大正贡献：若子树贡献为负数，则贪心放弃（与 $0$ 取 $\max$）；
经过当前根节点的最大路径和为：root->val + left_gain + right_gain，用其维护全局答案。

查看解题核心代码

class Solution {
    int max_sum = INT_MIN;
    int maxGain(TreeNode* root) {
        if (!root) return 0;
        int left = std::max(0, maxGain(root->left));
        int right = std::max(0, maxGain(root->right));
        max_sum = std::max(max_sum, root->val + left + right);
        return root->val + std::max(left, right);
    }
public:
    int maxPathSum(TreeNode* root) {
        maxGain(root);
        return max_sum;
    }
};

3. LeetCode 1245 - 树的直径 (Tree Diameter) `中等`¶

题意简述：给定一棵无向无环树的边集列表 edges，求该树的直径（最长简单路径的边数）。
算法核心：
标准多叉无向树直径模板题；
既可以运行两次 BFS（先从节点 $0$ 出发搜到最远点 $p$，再从 $p$ 出发搜到最远点 $q$ 返回距离）；
也可以通过一次 DFS 树形 DP，维护每个节点子树的最大深度 $d_1$ 和次大深度 $d_2$。

4. LeetCode 310 - 最小高度树 (Minimum Height Trees) `中等`¶

题意简述：选定树中某一个节点作为根，使得整棵树的高度最小。找出所有能够使得树高度最小的根节点列表。
算法核心：
本质是求解树的中心节点 (Tree Center)；
解法一（拓扑剥洋葱）：维护各节点度数，初始时将所有度数为 $1$ 的叶子节点入队，逐轮向内剥除，直到全图仅剩 $1$ 个或 $2$ 个节点即为答案；
解法二（直径中点法）：用两次 BFS 求出任一条直径的完整节点路径，取正中间的 $1$ 个或 $2$ 个节点返回。

查看解题核心代码 (拓扑剥洋葱法)

class Solution {
public:
    std::vector<int> findMinHeightTrees(int n, std::vector<std::vector<int>>& edges) {
        if (n == 1) return {0};
        std::vector<std::vector<int>> adj(n);
        std::vector<int> deg(n, 0);
        for (const auto &e : edges) {
            adj[e[0]].push_back(e[1]);
            adj[e[1]].push_back(e[0]);
            deg[e[0]]++;
            deg[e[1]]++;
        }

        std::queue<int> q;
        for (int i = 0; i < n; ++i) {
            if (deg[i] == 1) q.push(i);
        }

        int remaining = n;
        while (remaining > 2) {
            int sz = q.size();
            remaining -= sz;
            for (int i = 0; i < sz; ++i) {
                int u = q.front();
                q.pop();
                for (int v : adj[u]) {
                    if (--deg[v] == 1) {
                        q.push(v);
                    }
                }
            }
        }

        std::vector<int> ans;
        while (!q.empty()) {
            ans.push_back(q.front());
            q.pop();
        }
        return ans;
    }
};

5. LeetCode 2246 - 相邻字符不同的最长路径 (Longest Path With Different Adjacent Characters) `困难`¶

题意简述：给定一棵多叉有根树，每个节点分配有一个小写英文字母。求树中一条最长简单路径，使得路径上相邻两个节点的字符都不相同。返回路径包含的节点总数。
算法核心：
带有字符约束的树形 DP 直径模型；
递归遍历子节点 $v$：只有当 $s[u] \neq s[v]$ 时，子节点的分支链才能有效延伸至父节点 $u$；
维护有效分支的最大链长 $d_1$ 和次大链长 $d_2$；
穿过节点 $u$ 的最长合法路径节点数为 $d_1 + d_2 + 1$，全局取 $\max$。

6. LeetCode 3203 - 合并两棵树后的最小直径 (Find Minimum Diameter After Merging Two Trees) `困难`¶

题意简述：给定两棵独立的无向无环树，添加恰好一条边连接两棵树，求连接后新树直径的最小可能值。
算法核心：
直径合并理论的完美考察（定理 2 与树中心定理）；
分别求出两棵树的原直径 $D_1$ 和 $D_2$；
两树各选其中心节点进行连接，跨树的最长链为 $\lceil D_1 / 2 \rceil + \lceil D_2 / 2 \rceil + 1$；
最终答案为 $\max\left(D_1, \; D_2, \; \lfloor (D_1 + 1) / 2 \rfloor + \lfloor (D_2 + 1) / 2 \rfloor + 1\right)$。

查看解题核心代码

class Solution {
    int getDiameter(const std::vector<std::vector<int>>& edges) {
        int n = edges.size() + 1;
        std::vector<std::vector<int>> adj(n);
        for (const auto &e : edges) {
            adj[e[0]].push_back(e[1]);
            adj[e[1]].push_back(e[0]);
        }

        auto bfs = [&](int start) -> std::pair<int, int> {
            std::vector<int> dist(n, -1);
            std::queue<int> q;
            dist[start] = 0;
            q.push(start);
            int farthest = start;
            while (!q.empty()) {
                int u = q.front();
                q.pop();
                if (dist[u] > dist[farthest]) farthest = u;
                for (int v : adj[u]) {
                    if (dist[v] == -1) {
                        dist[v] = dist[u] + 1;
                        q.push(v);
                    }
                }
            }
            return {farthest, dist[farthest]};
        };

        int u = bfs(0).first;
        return bfs(u).second;
    }
public:
    int minimumDiameterAfterMerge(std::vector<std::vector<int>>& edges1, std::vector<std::vector<int>>& edges2) {
        int d1 = getDiameter(edges1);
        int d2 = getDiameter(edges2);
        int r1 = (d1 + 1) / 2;
        int r2 = (d2 + 1) / 2;
        return std::max({d1, d2, r1 + r2 + 1});
    }
};

7. LeetCode 1617 - 统计子树中城市之间最大距离 (Count Subtrees With Max Distance Between Cities) `困难`¶

题意简述：给定包含 $n \le 15$ 个节点的树。对于每个 $d \in [1, n - 1]$，统计满足以下条件的非空子图数量：该子图是原树的一棵子树，且子树中所有节点对之间的最大距离恰好等于 $d$。
算法核心：
数据范围 $n \le 15$，强力提示二进制状态压缩：枚举所有 $2^n - 1$ 个非空子集；
对于每个状态掩码 $mask$：
1. 连通性校验：利用 BFS 遍历验证该子集导出的子图是否连通（且边数等于点数减 $1$）；
2. 求子图直径：在子树内部通过两次 BFS 或树形 DP 求出子树的直径 $D$；
3. 若连通且直径为 $D$，则将计数器 ans[D - 1] 加 $1$。

树的直径 (Tree Diameter)¶

1. 核心定义与拓扑性质¶

1.1 基础定义¶

1.2 核心拓扑定理¶

2. 算法一：两次 DFS / BFS 算法与严格数学证明¶

2.1 算法流程¶

2.2 严格数学证明（反证法）¶

证明目标¶

分类讨论¶

情况 1：路径 \(u \leadsto p\) 与直径 \(A \leadsto B\) 有公共相交节点¶

情况 2：路径 \(u \leadsto p\) 与直径 \(A \leadsto B\) 无公共相交节点¶

3. 算法二：树形动态规划（Tree DP）算法¶

3.1 核心状态设计¶

3.2 状态转移方程¶

3.3 两种解法综合对比¶

4. 进阶拓扑性质与拓展应用¶

4.1 树的中心 (Tree Center) 与最小高度树¶

求解树中心的两种方法¶

4.2 两棵树合并后的新直径定理¶

定理推导与最优策略¶

5. 现代 C++ 规范实现模板¶

6. 精选 LeetCode 经典真题与解题提示¶

1. LeetCode 543 - 二叉树的直径 (Diameter of Binary Tree) `简单`¶

2. LeetCode 124 - 二叉树中的最大路径和 (Binary Tree Maximum Path Sum) `困难`¶

3. LeetCode 1245 - 树的直径 (Tree Diameter) `中等`¶

4. LeetCode 310 - 最小高度树 (Minimum Height Trees) `中等`¶

5. LeetCode 2246 - 相邻字符不同的最长路径 (Longest Path With Different Adjacent Characters) `困难`¶

6. LeetCode 3203 - 合并两棵树后的最小直径 (Find Minimum Diameter After Merging Two Trees) `困难`¶

7. LeetCode 1617 - 统计子树中城市之间最大距离 (Count Subtrees With Max Distance Between Cities) `困难`¶

算法指标	两次 DFS / BFS 算法	树形动态规划 (Tree DP)
时间复杂度	\(\mathcal{O}(V + E)\)（精确访问 \(2n\) 次）	\(\mathcal{O}(V + E)\)（精确访问 \(n\) 次）
空间复杂度	\(\mathcal{O}(n)\)	\(\mathcal{O}(n)\)（调用栈开销）
边权支持范围	仅限非负权边（\(w \ge 0\)）	支持任意实数边权（含负权）
点权支持能力	较繁琐（需转换边权）	极度天然支持（如 LC 124）
还原直径路径	极其容易（直接前驱回溯）	较繁琐（需额外记录转移来源）
树的中心提取	极度便捷（直接取路径中点）	需结合换根 DP 才能方便得到

树的直径 (Tree Diameter)¶

1. 核心定义与拓扑性质¶

1.1 基础定义¶

1.2 核心拓扑定理¶

2. 算法一：两次 DFS / BFS 算法与严格数学证明¶

2.1 算法流程¶

2.2 严格数学证明（反证法）¶

证明目标¶

分类讨论¶

情况 1：路径 \(u \leadsto p\) 与直径 \(A \leadsto B\) 有公共相交节点¶

情况 2：路径 \(u \leadsto p\) 与直径 \(A \leadsto B\) 无公共相交节点¶

3. 算法二：树形动态规划（Tree DP）算法¶

3.1 核心状态设计¶

3.2 状态转移方程¶

3.3 两种解法综合对比¶

4. 进阶拓扑性质与拓展应用¶

4.1 树的中心 (Tree Center) 与最小高度树¶

求解树中心的两种方法¶

4.2 两棵树合并后的新直径定理¶

定理推导与最优策略¶

5. 现代 C++ 规范实现模板¶

6. 精选 LeetCode 经典真题与解题提示¶

1. LeetCode 543 - 二叉树的直径 (Diameter of Binary Tree) 简单¶

2. LeetCode 124 - 二叉树中的最大路径和 (Binary Tree Maximum Path Sum) 困难¶

3. LeetCode 1245 - 树的直径 (Tree Diameter) 中等¶

4. LeetCode 310 - 最小高度树 (Minimum Height Trees) 中等¶

5. LeetCode 2246 - 相邻字符不同的最长路径 (Longest Path With Different Adjacent Characters) 困难¶

6. LeetCode 3203 - 合并两棵树后的最小直径 (Find Minimum Diameter After Merging Two Trees) 困难¶

7. LeetCode 1617 - 统计子树中城市之间最大距离 (Count Subtrees With Max Distance Between Cities) 困难¶

1. LeetCode 543 - 二叉树的直径 (Diameter of Binary Tree) `简单`¶

2. LeetCode 124 - 二叉树中的最大路径和 (Binary Tree Maximum Path Sum) `困难`¶

3. LeetCode 1245 - 树的直径 (Tree Diameter) `中等`¶

4. LeetCode 310 - 最小高度树 (Minimum Height Trees) `中等`¶

5. LeetCode 2246 - 相邻字符不同的最长路径 (Longest Path With Different Adjacent Characters) `困难`¶

6. LeetCode 3203 - 合并两棵树后的最小直径 (Find Minimum Diameter After Merging Two Trees) `困难`¶

7. LeetCode 1617 - 统计子树中城市之间最大距离 (Count Subtrees With Max Distance Between Cities) `困难`¶