[NOI2003] 逃学的小孩

形式化题目

给定一棵 $n$ 个节点的带权树。父母从家 $C$ 出发，先到离 $C$ 较近的朋友家（ $A$ 或 $B$ ），再去另一个朋友家。老师不知道 $C, A, B$ 的位置，求所有可能位置中父母花费时间的最大值。

思路

先看一个可以直接验证想法的朴素解：

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/**
 * 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-08-13 08:02
 * update_at: 2026-08-13 08:02
 */
// brute.cpp：小数据暴力解，枚举所有三点组合 (C, A, B) 直接算最坏时间。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 15;

int n, m;
vector<pair<int, ll> > g[MAXN]; // 邻接表：(邻居, 边权)

// 从 start 出发 BFS，返回 u 到 v 的距离。
ll bfs_dist(int start, int target) {
    queue<pair<int, ll> > q; // 队列元素：(节点, 距离)
    bool vis[MAXN] = {false};
    vis[start] = true;
    q.push(make_pair(start, 0));
    while (!q.empty()) {
        int u = q.front().first;
        ll d = q.front().second;
        q.pop();
        if (u == target)
            return d;
        for (int i = 0; i < (int)g[u].size(); i++) {
            int v = g[u][i].first;
            ll w = g[u][i].second;
            if (!vis[v]) {
                vis[v] = true;
                q.push(make_pair(v, d + w));
            }
        }
    }
    return -1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        g[u].push_back(make_pair(v, w));
        g[v].push_back(make_pair(u, w));
    }

    ll ans = 0;
    // 枚举 C、A、B 三个不同点，规则 1：先到距离近的点，再去远的点。
    for (int C = 1; C <= n; C++) {
        for (int A = 1; A <= n; A++) {
            if (A == C)
                continue;
            for (int B = 1; B <= n; B++) {
                if (B == C || B == A)
                    continue;
                ll dCA = bfs_dist(C, A);
                ll dCB = bfs_dist(C, B);
                ll dAB = bfs_dist(A, B);
                ll time = min(dCA, dCB) + dAB;
                if (time > ans)
                    ans = time;
            }
        }
    }
    cout << ans << '\n';
    return 0;
}

brute.cpp 枚举所有三点组合，每组 BFS 三次求距离再套公式， $O(n^4)$ ，只适合小数据。

关键化简有两步：

公式：先到近点再去远点，总时间恒等于

\min(d(C,A),\ d(C,B)) + d(A,B)

最优的 $A, B$ 是直径端点：设直径端点为 $A, B$ ，对任意点 $X$ 与任意点 $C$ ，把 $X$ 换成 $A$ 或 $B$ 不会使答案变小（ $X$ 到直径路径投影后，到直径端点的距离不小于到 $X$ 的距离），因此三元组最优解必取 $A, B$ 为直径端点。

于是做法是：三次 BFS——第一次从任意点找直径端点 $A$ ，第二次从 $A$ 找端点 $B$ 并得到 distA[]，第三次从 $B$ 得到 distB[]；最后扫描所有可能的 $C$ ：

\text{ans} = d(A,B) + \max_C \min(d(C,A),\ d(C,B))

以样例（链 $1\!-\!2\!-\!3\!-\!4$ ，边权 1）为例：直径端点 $A=1, B=4$ ，直径长 3。对 $C=2$ ： $\min(d(2,1), d(2,4)) = \min(1,2) = 1$ ，时间 $= 3 + 1 = 4$ ，这就是最大情况：父母先去近的 1 号点（1 分钟），再去 4 号点（3 分钟），共 4 分钟，与样例输出一致。

代码

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/**
 * 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-08-13 08:02
 * update_at: 2026-08-13 08:02
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 200005;

int n, m;
vector<pair<int, ll> > g[MAXN]; // 邻接表：(邻居, 边权)
ll distA[MAXN];                 // 各点到直径端点 A 的距离
ll distB[MAXN];                 // 各点到直径端点 B 的距离

// 从 start 出发 BFS 求最远点，并把距离写入 dist。
int bfs_farthest(int start, ll dist[]) {
    queue<int> q;
    for (int i = 1; i <= n; i++)
        dist[i] = -1;
    dist[start] = 0;
    q.push(start);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = 0; i < (int)g[u].size(); i++) {
            int v = g[u][i].first;
            ll w = g[u][i].second;
            if (dist[v] == -1) {
                dist[v] = dist[u] + w;
                q.push(v);
            }
        }
    }
    int far = start;
    for (int i = 1; i <= n; i++) {
        if (dist[i] > dist[far])
            far = i;
    }
    return far;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        g[u].push_back(make_pair(v, w));
        g[v].push_back(make_pair(u, w));
    }

    // 两次最远点搜索求直径端点 A、B。
    int A = bfs_farthest(1, distA);
    int B = bfs_farthest(A, distA);
    bfs_farthest(B, distB);

    // 对任意 C：时间 = dist(A,B) + min(dist(A,C), dist(B,C))，
    // 取 A、B 为直径端点时该值最大，答案 = 直径长 + max_C min(两个端点距离)。
    ll best_extra = 0;
    for (int i = 1; i <= n; i++) {
        ll mn = min(distA[i], distB[i]);
        if (mn > best_extra)
            best_extra = mn;
    }
    cout << distA[B] + best_extra << '\n';
    return 0;
}

复杂度

时间：三次 BFS $O(n)$ ，扫描 $O(n)$ 。
空间：邻接表与两个距离数组， $O(n)$ 。

总结

"三点最坏情况"类问题先做公式化简（ $\min$ + 路径和），再用树的直径把两个自由点固定成直径端点，剩下的单点扫描 $O(n)$ 。边权可能为 0，答案要用 64 位整数。

图示解析

这张 ASCII 图展示整道题的解题路线：

text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21朴素模拟（brute.cpp）
  枚举三点 (C, A, B)，每组 BFS 求距离
  时间 = min(d(C,A), d(C,B)) + d(A,B)        O(n^4)
        |
        | 瓶颈：三点组合太多，需要固定最优的 A、B
        v
关键引理
  对任意 X、Y，换成直径端点 A、B 后：
    min(d(C,X), d(C,Y)) + d(X,Y)
      <= min(d(C,A), d(C,B)) + d(A,B)
  因此最优的 A、B 是直径端点
        |
        v
三次 BFS（main.cpp）
  1. 任一点 BFS 定端点 A
  2. 从 A BFS 定端点 B，得 distA[]
  3. 从 B BFS 得 distB[]
  答案 = 直径长 + max_C min(distA[C], distB[C])
        |
        v
复杂度 O(n)，空间 O(n)

图中三条主线对应"暴力慢在哪"“为什么最优 A、B 是直径端点”“三次 BFS 如何同时拿到直径与全部距离”。核心是把三元组优化问题的枚举量从 $O(n^3)$ 压缩到 $O(n)$ 。