「一本通 5.2 练习 2」旅游规划

形式化题目

给定一棵包含 $n$ 个节点、 $n-1$ 条无向边的无权树（节点编号 $0, 1, \dots, n-1$ ）。

定义树的最长简单路径长度为树的直径。若节点 $u$ 位于树的至少一条最长简单路径上，则称 $u$ 位于最长路径上。要求按节点编号升序输出所有位于最长路径上的节点编号。

graph TD
    0((0)) --- 1((1))
    0 --- 2((2))
    0 --- 4((4))
    0 --- 6((6))
    0 --- 7((7))
    1 --- 3((3))
    2 --- 5((5))
    4 --- 8((8))
    6 --- 9((9))

    classDef onDiam fill:#d4edda,stroke:#28a745,stroke-width:2px;
    classDef notDiam fill:#f8d7da,stroke:#dc3545,stroke-width:2px;
    class 0,1,2,3,4,5,6,8,9 onDiam;
    class 7 notDiam;

图示说明：上图为输入样例的树结构。直径为 $4$ （如路径 $3 \to 1 \to 0 \to 2 \to 5$ ）。除了叶子节点 $7$ 到其他任意点的最长距离仅为 $3$ 外，其余 $9$ 个节点均在某条长度为 $4$ 的直径上。

正解

思路

1. 判定条件的数学转化

设整棵树的直径长度为 $D$ 。

对于任意节点 $u$ ，经过 $u$ 的最长简单路径必然由从 $u$ 出发走向两个不同相邻分支的最长链拼接而成（若 $u$ 为端点，则仅有一条分支延伸；若 $n=1$ ，长度为 $0$ ）。

如果经过节点 $u$ 的最长简单路径长度等于全树直径 $D$ ，则意味着存在一条包含 $u$ 的路径长度达到 $D$ ，即 $u$ 位于某条最长路径上。反之，由于全树不存在长度大于 $D$ 的路径，若 $u$ 位于最长路径上，经过 $u$ 的最长路径长度必然恰好为 $D$ 。

因此，问题转化为：计算每个节点 $u$ 经过两个不同邻居分支延伸出的最长简单路径长度，并判断其是否等于 $D$ 。

2. 两遍树形 DP（自底向上与自顶向下）

以节点 $0$ 为根将无向树转为有根树。对于每个节点 $u$ ，从它出发的路径方向分为两类：

向下延伸（进入子树）：
- $d_1[u]$ ：以 $u$ 为起点在 $u$ 的子树内延伸的最长链长度。
- $d_2[u]$ ：以 $u$ 为起点在 $u$ 的子树内、且与最长链不属于同一个直接子树分支的次长链长度。
- $c_1[u]$ ：取得最长链 $d_1[u]$ 的子节点编号。
向上延伸（进入父节点及祖先方向）：
- $up[u]$ ：从 $u$ 走向父节点并向树的其余部分延伸的最长链长度。

第一遍：自底向上（计算 $d_1, d_2, c_1$ ）

利用 BFS 遍历得到拓扑分层序列 order，然后逆序遍历 order：对每个节点 $u$ 及其子节点 $v$ ，令 $w = d_1[v] + 1$ ：

若 $w > d_1[u]$ ，则次长链更新为原最长链 $d_2[u] = d_1[u]$ ，最长链更新为 $d_1[u] = w$ ，并记录最优子分支 $c_1[u] = v$ ；
否则若 $w > d_2[u]$ ，则更新次长链 $d_2[u] = w$ 。

第二遍：自顶向下（计算 $up$ ）

正序遍历拓扑序列 order，由父节点 $u$ 向各个子节点 $v$ 转移：子节点 $v$ 向上延伸的最长链由两部分取最大值：

父节点继续向上延伸： $up[u] + 1$ ；
父节点拐入除 $v$ 以外的其他子树：
- 若 $v = c_1[u]$ （即 $v$ 本身是父节点向下最长链所在的子节点），则父节点只能使用次长链： $d_2[u] + 1$ ；
- 否则，父节点可以使用最长链： $d_1[u] + 1$ 。

即状态转移方程为：

up[v] = \max\Big(up[u] + 1,\, (d_2[u] \text{ if } c_1[u] = v \text{ else } d_1[u]) + 1\Big)

3. 直径与经过节点的最长路径计算

全树直径：
$D = \max_{0 \leqslant u < n} (d_1[u] + up[u])$
经过节点 $u$ 的最长路径：从 $u$ 相邻的所有可能分支中取最长的两条：向下最长链为 $d_1[u]$ ；第二长链可能来自向上祖先方向 $up[u]$ ，也可能来自另一子树分支 $d_2[u]$ 。两项之和即为：
$d_1[u] + \max(up[u],\, d_2[u])$
收集答案：检查所有满足 $d_1[u] + \max(up[u],\, d_2[u]) = D$ 的节点 $u$ ，按 $0$ 到 $n-1$ 的自然升序收集并输出即可。

代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 20:05
# update_at: 2026-09-30 20:05

import sys


def tree_dp(
    n: int, adj: list[list[int]], root: int = 0
) -> tuple[list[int], list[int], list[int], int]:
    """通过两遍树形 DP 计算每个节点向下最长/次长链、向上最长链及树的直径。"""
    parent = [-1] * n
    order = [root] * n
    head, tail = 0, 1
    while head < tail:
        u = order[head]
        head += 1
        for v in adj[u]:
            if v != parent[u]:
                parent[v] = u
                order[tail] = v
                tail += 1

    d1, d2, c1 = [0] * n, [0] * n, [-1] * n
    for u in reversed(order):
        p = parent[u]
        for v in adj[u]:
            if v != p and (w := d1[v] + 1) > d1[u]:
                d2[u], d1[u], c1[u] = d1[u], w, v
            elif v != p and w > d2[u]:
                d2[u] = w

    up = [0] * n
    for u in order:
        p, up_u, d1_u, d2_u, c1_u = parent[u], up[u], d1[u], d2[u], c1[u]
        for v in adj[u]:
            if v != p:
                best_down = d2_u if c1_u == v else d1_u
                up[v] = max(up_u + 1, best_down + 1)

    diameter = max(d1[u] + up[u] for u in range(n))
    return d1, d2, up, diameter


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    tokens = [int(x) for x in data]
    if not tokens:
        return
    n = tokens[0]

    adj: list[list[int]] = [[] for _ in range(n)]
    it = iter(tokens[1:])
    for u, v in zip(it, it):
        adj[u].append(v)
        adj[v].append(u)

    d1, d2, up, diameter = tree_dp(n, adj)
    ans = [u for u in range(n) if d1[u] + max(up[u], d2[u]) == diameter]
    print('\n'.join(map(str, ans)))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 10:02
 * update_at: 2026-10-05 10:02
 */
// main.cpp：两遍树形 DP 求树的直径，并输出所有位于最长路径上的节点。
// 做法：以 0 为根，自底向上求每个点子树内最长链 d1、次长链 d2（不同子树分支），
// 自顶向下求每个点向上的最长链 up；经过 u 的最长路径为 d1[u] + max(up[u], d2[u])，
// 等于直径 D 的点即为答案。
#include <bits/stdc++.h>
using namespace std;

/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-03-19 10:51
 * update_at: 2026-03-19 10:51
 */

typedef long long ll;

const int MAXN = 2e5 + 5;

int n;
vector<int> g[MAXN]; // g[u] = 节点 u 的相邻节点列表（无向树）
int parent[MAXN];    // BFS 后每个点的父节点，根的父节点为 -1
int order[MAXN];     // BFS 得到的拓扑分层序列，用于两遍扫描
ll d1[MAXN];         // d1[u]：u 在自己子树内向下延伸的最长链长度
ll d2[MAXN];         // d2[u]：u 子树内与最长链不同分支的次长链长度
int c1[MAXN];        // c1[u]：取得 d1[u] 的那个子节点
ll up[MAXN];         // up[u]：从 u 出发先向上走向父节点方向的最长链长度

// BFS 建立以 0 为根的父指针关系与遍历顺序，避免递归爆栈
void bfs_order() {
    for (int i = 0; i < n; i++) parent[i] = -1;
    int head = 0, tail = 0;
    order[tail++] = 0;
    parent[0] = -1;
    while (head < tail) {
        int u = order[head++];
        for (int i = 0; i < (int)g[u].size(); i++) {
            int v = g[u][i];
            if (v == parent[u]) continue;
            parent[v] = u;
            order[tail++] = v;
        }
    }
}

// 第一遍：逆序 BFS 序自底向上，计算 d1、d2、c1
void dp_bottom_up() {
    for (int i = 0; i < n; i++) {
        d1[i] = 0;
        d2[i] = 0;
        c1[i] = -1;
    }
    for (int i = n - 1; i >= 0; i--) {
        int u = order[i];
        for (int j = 0; j < (int)g[u].size(); j++) {
            int v = g[u][j];
            if (v == parent[u]) continue;
            ll w = d1[v] + 1; // 从 u 经子节点 v 向下走一步能达到的链长
            if (w > d1[u]) {  // 比最长链更长：原最长链降级为次长链
                d2[u] = d1[u];
                d1[u] = w;
                c1[u] = v;
            } else if (w > d2[u]) { // 只比次长链更长：更新次长链
                d2[u] = w;
            }
        }
    }
}

// 第二遍：正序 BFS 序自顶向下，计算每个点向上的最长链 up
void dp_top_down() {
    up[0] = 0;
    for (int i = 0; i < n; i++) {
        int u = order[i];
        for (int j = 0; j < (int)g[u].size(); j++) {
            int v = g[u][j];
            if (v == parent[u]) continue;
            // v 往上看：要么父节点继续向上，要么父节点拐进其它子树方向
            ll best_down = (c1[u] == v) ? d2[u] : d1[u];
            up[v] = max(up[u] + 1, best_down + 1);
        }
    }
}

int main() {
    if (scanf("%d", &n) != 1) return 0;
    for (int i = 1; i < n; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        g[u].push_back(v);
        g[v].push_back(u);
    }

    bfs_order();
    dp_bottom_up();
    dp_top_down();

    // 直径 D = 所有点的 d1 + up 的最大值
    ll diameter = 0;
    for (int i = 0; i < n; i++) diameter = max(diameter, d1[i] + up[i]);

    // 经过 u 的最长路径：向下最长链 + max(向上链, 子树内次长链)，等于 D 即在最长路径上
    for (int i = 0; i < n; i++) {
        ll longest_through = d1[i] + max(up[i], d2[i]);
        if (longest_through == diameter) printf("%d\n", i);
    }
    return 0;
}

复杂度

时间复杂度： $\mathcal{O}(n)$ 。BFS 序列获取、自底向上扫描与自顶向下扫描每个节点和每条边均被常数次访问，避免了递归函数调用的栈开销与深度限制。
空间复杂度： $\mathcal{O}(n)$ 。邻接表和 DP 数组长度均为 $n$ ，在 $n = 2 \times 10^5$ 时内存占用约 $70\text{ MB}$ ，完全在评测机限制内。

总结

本题利用了树的直径与简单路径的局部特征：经过一个节点的最长简单路径，等于从该节点出发向两个不同相邻分支延伸的最大长度之和。

借助经典的换根树形 DP 技术，自底向上维护子树最长/次长链，自顶向下转移补图向上最长链，仅用两次线性遍历就求出了全部节点在所有方向上的极值链长，实现了 $\mathcal{O}(n)$ 的最优时间复杂度。