树上问题的二级结论

第一章：树的基本概念回顾

在深入探讨高级结论之前，我们必须对树（Tree）这一数据结构有清晰的认识。树是一种非线性的数据结构，它由 $n$ 个有限节点组成一个具有层次关系的集合。

1.1 什么是树

在图论中，一个无向无环的连通图就被定义为一棵树。这个定义蕴含了树的几个基本特征：

• 节点 (Node/Vertex)：树的基本组成单位。
• 边 (Edge)：连接两个节点的路径。
• 对于一棵包含 $N$ 个节点的树，它有且仅有 $N-1$ 条边。
• 树中任意两个节点之间存在唯一的一条简单路径。

在算法竞赛中，我们常讨论有根树。有根树是指指定一个节点作为根节点 (Root)。一旦根被确定，其他概念也随之产生：

• 父节点 (Parent)：对于一个节点（非根节点），沿着路径走向根节点的第一个节点是它的父节点。
• 子节点 (Child): 如果 $u$ 是 $v$ 的父节点，那么 $v$ 就是 $u$ 的子节点。
• 叶节点 (Leaf)：没有任何子节点的节点。
• 深度 (Depth)：从根节点到某个节点所经过的唯一路径的边数。根节点的深度为0。
• 高度 (Height)：从某个节点到其最远叶节点路径的边数。树的高度等于根节点的高度。
• 子树 (Subtree)：由一个节点及其所有后代节点构成的树。

1.2 树的表示方法

在C++中，存储树最常用且高效的方法是邻接表 (Adjacency List)。对于每个节点，我们使用一个列表（如 std::vector）来存储所有与它直接相连的节点。

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 100005; // 假设节点数量上限
vector<int> adj[N]; // 邻接表, adj[u] 存储与 u 相连的所有节点

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n; // 节点数
    cin >> n;

    // 读入 n-1 条边
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u); // 无向图，需要加两条边
    }

    return 0;
}

• 代码解释：adj 是一个 vector 数组，adj[i] 本身是一个 vector，用于存放所有与节点 i 相邻的节点。这种表示方式只存储存在的边，空间效率高。
• 空间复杂度：$O(N+M)$，其中 $N$ 是节点数，$M$ 是边数。对于树而言，边数 $M = N-1$，所以是 $O(N)$。

1.3 树的遍历

遍历树是解决几乎所有树上问题的基础。

• 深度优先搜索 (DFS, Depth-First Search)：从根节点出发，尽可能深地搜索树的分支。当节点 $v$ 的所有边都已被探寻过，搜索将回溯到发现节点 $v$ 的节点。DFS 通常使用递归实现。
• 广度优先搜索 (BFS, Breadth-First Search)：从根节点开始，先访问所有距离根为1的节点，然后是距离为2的节点，以此类推，逐层向下访问。BFS 通常使用队列实现。

第二章：树的直径

树的直径是树上问题中一个非常基础且重要的概念，它的诸多二级结论是许多复杂问题的基石。

2.1 概念定义

树的直径是指树中任意两个节点之间最长简单路径的长度。这条路径的长度可以用路径上边的数量或边的权值之和来度量。若无特殊说明，我们通常指边的数量。

例如，一条链状的树，其直径就是链的长度，端点就是链的两个端点。

2.2 核心二级结论

关于树的直径，有两个至关重要的结论，它们是高效求解直径算法的理论基础。

• 二级结论 1: 从树上任意一个节点 $u$ 出发，进行一次深度优先搜索或广度优先搜索，找到距离它最远的节点 $v$。那么，节点 $v$ 必定是该树某条直径的一个端点。

• 二级结论 2: 接着从上一结论找到的端点 $v$ 出发，再次进行一次搜索，找到距离 $v$ 最远的节点 $w$。那么，$v$ 到 $w$ 的路径就是树的一条直径。

这两个结论的强大之处在于，它们将一个看似需要枚举所有点对 $O(N^2)$ 的问题，简化为了两次遍历全树 $O(N)$ 的问题。

2.3 求解算法

根据上述结论，我们主要有两种求解树的直径的常用算法。

2.3.1 两遍DFS/BFS法

这是最直观且最常用的求解树直径（及端点）的方法。

算法步骤：

1. 从图中任意选取一个起始点 $S$。
2. 从点 $S$ 开始执行一次DFS或BFS，找出距离 $S$ 最远的节点 $U$。根据结论1，$U$ 必为某条直径的一个端点。
3. 从点 $U$ 开始再执行一次DFS或BFS，找出距离 $U$ 最远的节点 $V$。
4. 节点 $U$ 和 $V$ 之间的路径就是树的一条直径，它们之间的距离就是直径的长度。

C++ 代码示例：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 100005;
vector<pair<int, int>> adj[N]; // 边带权的情况，存储 {邻接点, 边权}
int dis[N]; // 存储距离
int n;

void dfs(int u, int p) { // u: 当前节点, p: 父节点
    for (auto& edg : adj[u]) {
        int v = edg.first;
        int w = edg.second;
        if (v == p) continue; // 避免走回头路
        dis[v] = dis[u] + w;
        dfs(v, u);
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n;
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        // 假设边权为1
        int w = 1;
        cin >> u >> v;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    // 第一次DFS
    memset(dis, 0, sizeof(dis));
    dfs(1, 0); // 从任意点1开始，父节点设为0
    
    int u = 1;
    for (int i = 1; i <= n; ++i) {
        if (dis[i] > dis[u]) {
            u = i; // 找到最远点 u
        }
    }

    // 第二次DFS
    memset(dis, 0, sizeof(dis));
    dfs(u, 0); // 从 u 开始

    int v = u;
    for (int i = 1; i <= n; ++i) {
        if (dis[i] > dis[v]) {
            v = i; // 找到距离u的最远点v
        }
    }
    
    cout << "Diameter is " << dis[v] << endl;
    cout << "Endpoints are " << u << " and " << v << endl;

    return 0;
}

• 题意概括：给定一棵无权树，求其直径长度及任意一对端点。
• 代码解释：dfs(u, p) 函数计算从起始点到树上所有其他点的距离。第一次 dfs 从任意点（这里是1）开始，找到最远点 u。第二次 dfs 从 u 开始，找到距离 u 的最远点 v，dis[v] 即为直径长度。
• 复杂度分析：
  • 时间复杂度：$O(N)$。两次DFS都只访问每个节点和每条边常数次。
  • 空间复杂度：$O(N)$。用于存储邻接表和 dis 数组。

2.3.2 树形动态规划 (DP) 法

树形DP是解决树上问题的强大工具，同样可以用来求解直径。这种方法对于处理更复杂的问题变种时更具扩展性。

核心思想：对于树中的任意一个节点 $u$，经过该节点的最长路径长度，等于从 $u$ 出发往下走的两条最长路径之和。

状态定义：

• $d_1[u]$：表示以 $u$ 为根的子树中，从 $u$ 出发向下的最长路径长度。
• $d_2[u]$：表示以 $u$ 为根的子树中，从 $u$ 出发向下的次长路径长度。

状态转移： 我们对树进行一次DFS，在回溯的过程中计算这两个值。对于节点 $u$ 和它的一个子节点 $v$：

• 从 $v$ 可以向上延伸一条长度为 $d_1[v] + w(u,v)$ 的路径到 $u$。
• 我们用所有子节点延伸上来的路径长度来更新 $u$ 的 $d_1[u]$ 和 $d_2[u]$。
• 在更新完所有子节点后， $d_1[u] + d_2[u]$ 就是经过节点 $u$ 的最长路径。
• 我们用所有节点的 $d_1[u] + d_2[u]$ 的最大值来更新全局的直径长度。

C++ 代码示例：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 100005;
vector<pair<int, int>> adj[N];
int ans = 0; // 全局变量，记录直径长度

// 返回以u为根的子树中，从u出发向下的最长路径
int dfs(int u, int p) {
    int d1 = 0; // 最长
    int d2 = 0; // 次长
    for (auto& edg : adj[u]) {
        int v = edg.first;
        int w = edg.second;
        if (v == p) continue;
        
        int len = dfs(v, u) + w;
        if (len >= d1) {
            d2 = d1;
            d1 = len;
        } else if (len > d2) {
            d2 = len;
        }
    }
    
    ans = max(ans, d1 + d2); // 尝试用经过u的最长路径更新答案
    return d1; // 返回u向下的最长路径给父节点
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        int w = 1;
        cin >> u >> v;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    dfs(1, 0); // 从任意点开始DP
    cout << "Diameter is " << ans << endl;

    return 0;
}

• 题意概括：用树形DP求解树的直径长度。
• 代码解释：dfs(u, p) 函数在后序遍历的位置进行计算。它递归地计算所有子节点 v 向下的最长路径，并用 dfs(v, u) + w 来更新当前节点 u 的最长 (d1) 和次长 (d2) 向下路径。d1 + d2 就是穿过 u 的最长路径，用它来更新全局答案 ans。函数返回 d1 以供 u 的父节点使用。
• 复杂度分析：
  • 时间复杂度：$O(N)$。每个节点只被访问一次。
  • 空间复杂度：$O(N)$。用于邻接表和递归栈。

笔试题应用：

• 选择题：“从树上任意一点出发能到达的最远点，一定是直径的端点”，这个结论本身就是常考点。
• 判断题：“树的直径是唯一的”，此说法错误，长度唯一的直径路径可能有多条。
• 程序填空：常常给出两遍DFS法或树形DP法的不完整代码，要求补全关键的逻辑部分，如更新最远点、DP状态转移等。

第三章：树的中心与重心

树的中心和重心是两个描述树“平衡性”或“几何中心”的概念，它们定义不同，性质各异，但都非常重要。

3.1 树的中心

3.1.1 概念定义

树的中心 (Center)：对于树中的一个节点 $u$，我们计算它到树中所有其他节点 $v$ 的距离，并取其中的最大值，这个值称为节点 $u$ 的偏心率 (Eccentricity)，记为 $E(u) = \max_{v \in V} dist(u, v)$。 树的中心就是偏心率最小的节点。即，若节点 $c$ 是中心，则 $E(c) \le E(u)$ 对所有节点 $u$ 成立。

通俗地讲，树的中心是这样一个点，它使得离它最远的那个点到它的距离，在所有节点中是最小的。

3.1.2 核心二级结论

• 二级结论 1: 一棵树有一个或两个中心。如果是一条链，偶数个点时中心有两个，奇数个点时中心有一个。
• 二级结论 2: 树的所有中心都位于该树的某条直径上。
• 二级结论 3: 如果树有两个中心，那么这两个中心必定是相邻的。
• 二级结论 4: 寻找树的中心，可以通过一个类似“拓扑排序”的迭代过程实现：每一轮都删除树中所有的叶节点，直到最后剩下一个或两个节点为止，这些剩下的节点就是树的中心。

3.1.3 求解算法

基于上述结论，我们有两种主要的求解方法。

方法一：利用直径

1. 使用“两遍DFS/BFS法”找到树的一条直径 $U-V$ 及其路径。
2. 找到这条路径的中点。如果直径长度为 $L$，那么中点就是从 $U$ (或$V$) 出发，在路径上走 $\lfloor L/2 \rfloor$ 和 $\lceil L/2 \rceil$ 步到达的节点。
   • 若直径长度为偶数，则有两个中心。
   • 若直径长度为奇数，则只有一个中心。

方法二：叶节点删除法 (拓扑排序思想)

1. 计算所有节点的度数。
2. 将所有度数为1的节点（叶节点）加入一个队列。
3. 当队列不为空时，循环执行： a. 弹出队头节点 $u$。 b. 对于 $u$ 的每一个邻居 $v$，将 $v$ 的度数减1。 c. 如果 $v$ 的度数变为1，则将 $v$ 入队。
4. 最后被删除的（即最后留在图中的）一或两个节点，就是树的中心。

C++ 代码示例（叶节点删除法）：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 100005;
vector<int> adj[N];
int deg[N]; // 存储度数

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    if (n == 1) {
        cout << 1 << endl;
        return 0;
    }
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        deg[u]++;
        deg[v]++;
    }

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

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

    cout << "Center(s): ";
    while (!q.empty()) {
        cout << q.front() << " ";
        q.pop();
    }
    cout << endl;

    return 0;
}

• 题意概括：用不断删除叶节点的方法找到树的中心。
• 代码解释：deg 数组记录每个点的度数。初始时，将所有叶节点（度为1）入队。rem 记录还未被删除的节点数。每一轮循环，将当前队列中所有的叶节点一次性“删除”，并将其邻居的度数减一。如果邻居变成了新的叶节点，则入队。循环直到图中剩余节点不多于2个，此时队列中的节点即为中心。
• 复杂度分析：
  • 时间复杂度：$O(N)$。每个节点和边最多被访问一次。
  • 空间复杂度：$O(N)$。用于邻接表、度数数组和队列。

3.2 树的重心

3.2.1 概念定义

树的重心 (Centroid)：对于树中的一个节点 $u$，如果我们将它从树中删除，树会分裂成若干个连通分量（子树）。我们取这些连通分量中节点数最大的那个，其大小记为 $S(u)$。 树的重心就是使得 $S(u)$ 最小的那个节点。

通俗地讲，重心是树的一个“平衡点”，删除它后，产生的各个小块树的大小都相对均匀，不会出现一个特别大而其他特别小的情况。

3.2.2 核心二级结论

• 二级结论 1: 删除重心后，其所有子树的大小（包括来自父节点方向的那个“子树”）都不超过 $\lfloor (N-1)/2 \rfloor$。这是重心中最重要的性质。对于有根树，是任何一个子树的大小都不超过 $\lfloor N/2 \rfloor$。
• 二级结论 2: 一棵树有一个或两个重心。如果有两个，它们必定相邻。
• 二级结论 3: 树的重心不一定在直径上。这是一个区别于中心的重要特征。
• 二级结论 4: 向树中添加或删除一个叶子，重心最多移动一条边的距离。
• 二级结论 5: 所有重心到其他所有节点的距离之和是最小的。即若 $g$ 为重心，则 $\sum_{v \in V} dist(g, v)$ 最小。

3.2.3 求解算法

求解重心通常通过一次DFS完成。

算法步骤：

1. 任意选取一个根节点，对整棵树进行一次DFS。
2. 在DFS的过程中，对于每个节点 $u$，计算出以它为根的子树的大小 size[u]（包括它自己）。
3. DFS回溯到节点 $u$ 时，我们可以计算出删除 $u$ 后产生的各个子树的大小：
   • 对于 $u$ 的每个子节点 $v$，会产生一个大小为 size[v] 的子树。
   • 还会产生一个连接到 $u$ 的父节点的连通分量，其大小为 N - size[u]。
4. 找出这些子树大小中的最大值，即为 $S(u)$。
5. 遍历所有节点，找到使 $S(u)$ 最小的节点，即为重心。

C++ 代码示例：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 100005;
vector<int> adj[N];
int sz[N]; // sz[u] 存储以u为根的子树大小
int n;
int min_s = N, ans_node; // min_s记录最小的最大子树大小, ans_node记录重心

void dfs(int u, int p) {
    sz[u] = 1;
    int max_sub = 0; // 记录u的最大子树大小
    for (int v : adj[u]) {
        if (v == p) continue;
        dfs(v, u);
        sz[u] += sz[v];
        max_sub = max(max_sub, sz[v]);
    }
    max_sub = max(max_sub, n - sz[u]); // 来自父方向的子树
    
    if (max_sub < min_s) {
        min_s = max_sub;
        ans_node = u;
    } else if (max_sub == min_s) {
        // 如果有两个重心，可以选择编号较小的或都记录
        ans_node = min(ans_node, u);
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    dfs(1, 0); // 从任意点1开始
    
    cout << "Centroid is " << ans_node << endl;
    cout << "Its max subtree size is " << min_s << endl;

    return 0;
}

• 题意概括：通过一次DFS计算每个节点的子树大小，从而找出树的重心。
• 代码解释：dfs(u, p) 函数在后序遍历位置计算 sz[u]。同时，对于每个 u，计算其最大子树 max_sub。max(max_sub, n - sz[u]) 是删除 u 后所有连通分量大小的最大值。我们用这个值来更新全局最优解 min_s 和对应的重心 ans_node。
• 复杂度分析：
  • 时间复杂度：$O(N)$。一次DFS。
  • 空间复杂度：$O(N)$。用于邻接表、sz数组和递归栈。

第四章：最近公共祖先 (LCA)

最近公共祖先（Lowest Common Ancestor, LCA）是处理有根树上路径问题的核心工具。

4.1 概念定义

在一棵有根树中，节点 $u$ 和节点 $v$ 的公共祖先是指一个节点，它既是 $u$ 的祖先，也是 $v$ 的祖先。最近公共祖先 $LCA(u, v)$ 则是指所有公共祖先中，深度最大的那一个。

LCA也可以被理解为：从根节点到 $u$ 的路径和从根节点到 $v$ 的路径，在分叉前的最后一个交汇点。

4.2 核心二级结论与性质

LCA的应用价值主要体现在它与路径、距离等概念的紧密联系上。

• 二级结论 1 (距离公式)：树上两点 $u, v$ 之间的距离可以通过它们的深度和它们LCA的深度来计算：

  $$dist(u, v) = dist(root, u) + dist(root, v) - 2 \times dist(root, LCA(u, v)) $$

  如果边权为1，则公式简化为：

  $$dist(u, v) = depth(u) + depth(v) - 2 \times depth(LCA(u, v)) $$

  这个公式将求两点距离的问题转化为了求LCA的问题。

• 二级结论 2: $u$ 到 $v$ 的唯一简单路径，一定包含 $LCA(u, v)$。并且，$LCA(u, v)$ 是这条路径上深度最小（最靠近根）的节点。

4.3 求解算法

求解LCA有多种算法，效率各不相同。

4.3.1 向上标记法（暴力）

这是一个简单直观但效率较低的方法，适合在笔试中理解概念或处理小数据。

算法步骤：

1. 先从节点 $u$ 开始，不断地沿着父指针向上走到根节点，并标记所有经过的节点。
2. 再从节点 $v$ 开始，同样沿着父指针向上走，遇到的第一个被标记过的节点，就是 $LCA(u, v)$。

复杂度分析: 最坏情况下，每次查询都需要遍历到根，时间复杂度为 $O(N)$。对于多次查询，总效率低下。

4.3.2 倍增法 (Binary Lifting)

倍增法是一种非常经典且高效的在线查询LCA的算法，它通过预处理来加速查询过程。

核心思想： 我们不希望一步一步地向上跳，而是希望能够一次性向上跳一大步。倍增法预处理出一个数组 $fa[i][j]$，表示从节点 $i$ 向上走 $2^j$ 步所能到达的祖先。

预处理步骤 ($O(N \log N)$)：

1. 首先通过一次DFS（或BFS）计算出每个节点的深度 dep[i] 和它的直接父节点 fa[i][0]。
2. 然后通过动态规划来计算 $fa$ 数组：$$fa[i][j] = fa[fa[i][j-1]][j-1]$$ 这个公式的含义是：从 $i$ 向上走 $2^j$ 步，等于先从 $i$ 向上走 $2^{j-1}$ 步到达 $fa[i][j-1]$，再从这个新位置继续向上走 $2^{j-1}$ 步。

查询步骤 ($O(\log N)$)： 假设要查询 $LCA(u, v)$。

1. 拉到同一深度：首先，我们总是希望从较深的点开始跳。假设 dep[u] < dep[v]，我们先将 $v$ 向上跳 dep[v] - dep[u] 步，使其与 $u$ 在同一深度。这一跳跃过程可以通过二进制拆分高效完成：从大到小枚举 $j$，如果 dep[v] - (1 << j) >= dep[u]，就令 $v = fa[v][j]$。
2. 判断是否重合：如果此时 $u$ 和 $v$ 已经是同一个节点，那么这个节点就是它们的LCA。
3. 同步向上跳：如果 $u \neq v$，说明LCA还在它们的上方。现在它们在同一深度，我们可以让它们同步向上跳。我们从大到小枚举 $j$，只要 $fa[u][j]$ 不等于 $fa[v][j]$，就说明它们可以一起向上跳 $2^j$ 步而不会错过LCA。令 $u = fa[u][j]$，$v = fa[v][j]$。
4. 当循环结束后，$u$ 和 $v$ 的父节点 fa[u][0] (或 fa[v][0]) 就是它们的LCA。

C++ 代码示例（倍增法）：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 100005;
const int LOGN = 17; // log2(N)
vector<int> adj[N];
int dep[N], fa[N][LOGN + 1];

void dfs(int u, int p) {
    dep[u] = dep[p] + 1;
    fa[u][0] = p;
    for (int i = 1; i <= LOGN; ++i) {
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
    }
    for (int v : adj[u]) {
        if (v == p) continue;
        dfs(v, u);
    }
}

int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v); // 保证u更深
    
    for (int i = LOGN; i >= 0; --i) {
        if (dep[fa[u][i]] >= dep[v]) {
            u = fa[u][i];
        }
    }
    
    if (u == v) return u;
    
    for (int i = LOGN; i >= 0; --i) {
        if (fa[u][i] != fa[v][i]) {
            u = fa[u][i];
            v = fa[v][i];
        }
    }
    return fa[u][0];
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, q; // n节点数, q查询次数
    cin >> n >> q;
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    dfs(1, 0); // 预处理

    while (q--) {
        int u, v;
        cin >> u >> v;
        int ans = lca(u, v);
        cout << ans << endl;
    }

    return 0;
}

• 题意概括：给定一棵有根树和多次查询，每次查询两个节点的最近公共祖先。
• 代码解释：dfs 函数用于预处理 dep 数组和 fa 数组。lca(u,v) 函数实现了倍增法的查询逻辑。先将两点调到同一深度，然后同步向上跳，直到它们的父节点相同。
• 复杂度分析：
  • 预处理时间复杂度：$O(N \log N)$。
  • 单次查询时间复杂度：$O(\log N)$。
  • 空间复杂度：$O(N \log N)$，用于存储 fa 数组。

笔试题应用:

• 程序阅读/填空：倍增法LCA的模板是常见的考察对象，特别是 fa[u][i] = fa[fa[u][i-1]][i-1] 这个核心转移方程，以及查询时两个循环的逻辑。
• 计算题：给出小规模的树，要求手动找出LCA，或利用距离公式 $dist(u, v) = dep(u) + dep(v) - 2 \times dep(lca(u,v))$ 计算两点距离。

第五章：总结与练习

5.1 知识点梳理

概念	定义	核心二级结论/性质	常用求解算法
树的直径	树上最长简单路径	1. 任一点最远点必为直径端点。 2. 两遍搜索可确定直径。	两遍DFS/BFS, 树形DP
树的中心	偏心率最小的节点	1. 1或2个，必相邻。 2. 必在直径上。 3. 可通过不断删叶节点找到。	利用直径, 删叶子法
树的重心	使最大子树最小的节点	1. 1或2个，必相邻。 2. 删除后最大子树大小 $\le \lfloor N/2 \rfloor$ 。 3. 到所有点距离和最小。	DFS求子树大小
LCA	深度最大的公共祖先	1. $dist(u,v) = dep(u)+dep(v)-2dep(lca)$ 2. $u-v$ 路径上深度最小的点。	暴力向上跳, 倍增法

5.2 典型试题分析

选择题

例1：关于一棵 $N$ 个节点的无权树，下列说法正确的是？ A. 树的直径唯一。 B. 树的重心一定在直径上。 C. 从任意节点出发进行BFS，最后访问到的节点一定是直径的端点。 D. 删除树的重心后，剩余各个连通分量的大小均不超过 $N/2$。

分析： A. 错误。直径的长度是唯一的，但满足此长度的路径可能有多条。 B. 错误。这是一个经典误区，重心和中心不同，重心不一定在直径上。 C. 错误。应该是距离最远的节点，而不是最后访问的。BFS的访问顺序与距离有关，但“最后访问”不等于“距离最远”。 D. 正确。这是树的重心的核心性质。

答案：D

判断题

例2：一棵树的中心和重心在任何情况下都是同一个节点。 (×)

分析：错误。在很多不对称的树结构中，中心和重心会是不同的节点。例如，一个节点 $u$ 连接着一条长链和一个很大的“星形”结构，重心可能被拉向星形结构一侧，而中心则可能在长链上。

程序阅读与填空

例3：下面是用树形DP求解树的直径的代码片段，请补全空白处。

// ... (邻接表等定义)
int ans = 0;

int dfs(int u, int p) {
    int d1 = 0, d2 = 0;
    for (auto& edg : adj[u]) {
        int v = edg.first;
        int w = edg.second;
        if (v == p) continue;
        
        int len = dfs(v, u) + w;
        if (len >= d1) {
            d2 = d1;
            d1 = len;
        } else if (len > d2) {
            d2 = len;
        }
    }
    
    // 空白处
    __________________;
    
    return d1;
}

分析：该 dfs 函数的目的是计算并返回从 u 向下的最长路径长度 (d1)。在计算完所有子节点贡献的路径后，d1 和 d2 分别是经过 u 向下的最长和次长路径。此时，经过节点 u 的最长路径长度就是 d1 + d2。我们需要用这个值来更新全局的直径答案 ans。

答案：ans = max(ans, d1 + d2);