答案 = 直径长 + max_u min(d(u,A), d(u,B)); 三臂分解得主干与支链折返，配合极简树上上界与无需证明直径的换根 DP 双解法.
OJ: luogu
题目 ID: P4408
难度:提高
标签:树的直径BFS贪心树形DP换根DP
创建: 2026-07-17 02:00
更新: 2026-10-26 21:37
形式化题目
给定一棵带非负边权的树. 取三个互不相同的节点: 家
求所有三点选取中
样例
样例 in1 是一条链
| 家 |
时间 |
|||
|---|---|---|---|---|
| 1 | 0 | 3 | 0 | 3 |
| 2 | 1 | 2 | 1 | 4 |
| 3 | 2 | 1 | 1 | 4 |
| 4 | 3 | 0 | 0 | 3 |
朋友取直径两端
暴力解法
思路
最直接的做法是把定义照抄一遍: 枚举所有三点组合
代码
/**
* 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-10-26 20:33
*/
// brute.cpp：小数据暴力解，枚举所有三点组合 (C, A, B)，按定义直接算最坏时间。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 15;
struct Edge {
int to; // 邻居节点
ll w; // 边权
};
int n, m;
vector<Edge> g[MAXN]; // 邻接表：g[u] 是节点 u 连出的所有边
// 从 start 出发 BFS，返回到 target 的距离（树连通，一定可达）。
// 图为树，路径唯一，首次到达即最短距离，因此不需要 Dijkstra。
ll bfs_dist(int start, int target) {
ll dist[MAXN];
for (int i = 1; i <= n; i++)
dist[i] = -1; // 用 -1 当"未访问"标记：边权可以为 0
dist[start] = 0;
queue<int> q;
q.push(start);
while (!q.empty()) {
int u = q.front();
q.pop();
if (u == target)
return dist[u];
for (auto &e : g[u]) {
if (dist[e.to] == -1) {
dist[e.to] = dist[u] + e.w;
q.push(e.to);
}
}
}
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({v, w});
g[v].push_back({u, w});
}
ll ans = 0;
// 枚举家 C 与两个朋友 A、B，三者互不相同。
// 规则 1：先到离 C 较近的朋友，再去另一个，所以时间 = min(d(C,A), d(C,B)) + d(A,B)。
for (int C = 1; C <= n; C++) {
for (int A = 1; A <= n; A++) {
if (A == C)
continue;
for (int B = A + 1; B <= n; B++) {
if (B == C)
continue;
ll dCA = bfs_dist(C, A);
ll dCB = bfs_dist(C, B);
ll dAB = bfs_dist(A, B);
ll cost = min(dCA, dCB) + dAB;
if (cost > ans)
ans = cost;
}
}
}
cout << ans << '\n';
return 0;
}brute.cpp 对每组三点各做一次遍历求距离, 完全按定义结算, 不依赖任何还没证明的公式. 它的价值在于给出可信的小数据基准.
复杂度
枚举
瓶颈
三点组合太多. 如果能把某两个点固定成与
解法总览
两条路线都是
| 解法 | 核心观察 | 复杂度 | 适用场景 | 对应代码 |
|---|---|---|---|---|
| 一、直径端点 | 先证最优解的两个朋友可以取直径两端，答案化简为 |
需要一次几何上界证明；代码最短，三次遍历加一次扫描 | main.cpp / main.py |
|
| 二、树形换根 DP | 不碰直径，在每个节点汇总向外的前三长链 |
不想证贪心结论，只需树形 DP 基本功 | main2.cpp |
正式主解是解法一（main.cpp，附同算法的 Python 版 main.py）：证明虽多一步，但它直接回答了「为什么是直径端点」，并且把求解压成三次遍历加一次扫描，常数最小、最好写。
如果不想碰任何几何论证，解法二是纯机械路线：枚举汇合中心点之后，题目要求的时间恰好是「一条主干道走一次 + 一条支链折返走两次」，于是每个点只需知道向外伸出的前三条独立长链。两条路线互不依赖，不构成前后优化关系。
解法一：直径端点贪心（主解）
思路
这道解法最核心的问题是：为什么最优解里的两个朋友，可以固定为树的某条直径的两个端点？
只要这个结论成立，两个朋友
注意：我们不能靠「一步步贪心拉伸」来论证（因为向最远点替换某个朋友时，汇合中心点可能漂移，两朋友甚至可能折叠变近，单步替换并不保序）。正确的思路是为任意三点计算一个全树统一的天花板上界，并证明选直径端点正好能顶满这个天花板。
整个论证分为清晰的三步：
第一步：三叉臂展开（物理意义）
无论选哪三点
按题意，父母先去近的朋友
仔细观察这个形式
：这是从家 一路直达朋友 的主干路径（只走一次）； ：是在途经汇合点 时，向旁边伸出去看望朋友 ，然后原路退回 的侧向支链（走了一个来回折返，即走两次）。
第二步：树上任意三链的天然上界
设整棵树的直径长度为
三叉臂中的两条链与单条链有天然的长度封顶：
- 主干道长度：
是树上的一条简单路径，因此显然： - 折返短臂
的长度： 汇合中心点 无论在树的哪个位置，它向外伸出的任意分支长度 ，都不可能超过 到直径两端较近者的距离（即 ）。 证明：若不然，假设 。那么不妨设 （即 是较远端），此时 的长度至少为 。由于直径是树上最长路径，从 沿着伸出 的分支走到底，与 拼成的新路径长度为 ，这与 是全树直径矛盾！ 因此必有：
第三步：合并结论（全树天花板）
先把第二步的两条封顶直接相加，得到一个很松的上界：
这个界比真实上界多出了一个
因为
式中
- 最大值不会超过直径：
。 - 最小值不会超过
，这一条需要单独证。
把每个点按它离直径哪一端更近分成两类：
同侧引理：若
证明：把
这两个数分别描述「
树中两点之间的唯一路径必经过各自的投影点，而
另外，离开直径的分支深度不会超过投影点到端点的距离，即
又因为
抽屉原理挑出的
把它和
这个上界对任意三点组合
由此严谨证明：在全局最优解中，两个朋友一定可以取为直径的两个端点
警示：一个流传极广的“伪直觉证明”及其致命反例
许多人在初学此题时，常会产生一个看似极其简洁、顺理成章的“直觉证明”：
「固定家
- 为了让第一步尽可能长，从
出发显然应该走到离 最远的点，由两次 DFS 求直径的定理，这个最远点 一定是某条直径的端点； - 接下来从
走到 ，为了让第二步尽可能长，显然应该走到离 最远的点，也就是直径的另一端点 。 - 综上，两朋友
必然是直径的两端。」
这个证明非常符合人的直觉，甚至很多博客和讨论区都在使用，但它在逻辑上是完全错误的！主要有两大漏洞：
- 违背规则定义：
题目的规则是先去较近的朋友（式中为
）。如果让 成为离 最远的点，那只要另一个朋友 离 稍微近一点，父母根本不会先去 ，而是会先去 。此时走的是 ，你以为被算入折返的第一步根本没生效。 - 目标不是单步最大化，局部贪心不保序：
总路程是两段的和，为了追求第一步大，可能会导致两朋友之间的距离
剧烈缩水，导致总和变小。
精确反例（固定
树的边权：
1-2(28) 1-3(45) 2-4(18) 2-5(38) 1-6(21) 1-7(2) 1-8(42) 1-9(25) 4-10(28) 1-11(34)
整棵树的唯一直径是 10 到 3，长 D = 119。两端点为 A = 10, B = 3。若我们固定家在
- 离
最远的点确实是直径端点 （ ）； - 离
最远的点也确实是直径端点 （ ）； - 按直觉伪证选直径端点
： - 但如果不选直径端点，而是选
：
核心警示：
本题成立的命题是**「全树全局最大值可以由直径端点配上某个特定的
算法步骤
- 从任意节点（如节点
）出发跑一次 BFS/DFS，找到距离最远的点，记为直径端点 。 - 从
出发跑一次 BFS/DFS，记录每个点到 的距离 distA[]，距离最远的点即为直径另一端点 （此时直径长 ）。 - 从
出发再跑一次 BFS/DFS，记录每个点到 的距离 distB[]。 - 扫描所有节点
，计算 的最大值，加上 即为答案。
代码
/**
* 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-10-26 20:33
*/
// main.cpp：三次 BFS 求直径端点与两端距离数组，再 O(n) 扫描答案。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 200005;
struct Edge {
int to; // 邻居节点
ll w; // 边权
};
int n, m;
vector<Edge> g[MAXN]; // 邻接表：g[u] 是节点 u 连出的所有边
ll distA[MAXN]; // 各点到直径端点 A 的距离
ll distB[MAXN]; // 各点到直径端点 B 的距离
// 从 start 出发 BFS，把到各点的距离写入 dist，返回距离最远的节点编号。
// 因为是树, 所以用 BFS 求路径长度即可（路径唯一，不需要 Dijkstra）。
int bfs_farthest(int start, ll dist[]) {
queue<int> q;
for (int i = 1; i <= n; i++)
dist[i] = -1; // 用 -1 当"未访问"标记：边权可以为 0，不能用 0 标记
dist[start] = 0;
q.push(start);
while (!q.empty()) {
int u = q.front();
q.pop();
for (auto &e : g[u]) {
if (dist[e.to] == -1) {
dist[e.to] = dist[u] + e.w;
q.push(e.to);
}
}
}
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({v, w});
g[v].push_back({u, w});
}
// 两次最远点搜索求出一对直径端点 A、B。
int A = bfs_farthest(1, distA);
int B = bfs_farthest(A, distA); // 这次的距离以 A 为源，正好是 distA[]
bfs_farthest(B, distB);
// 答案是「直径长 + 到两端较近距离的最大值」。
// 注意直径端点这一对朋友只保证全局最优，对每个固定的家未必最优。
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;
}同一算法的 Python 版, 便于对照阅读:
"""P4408 逃学的小孩：与 main.cpp 同一算法的 Python 版。
三次遍历求出一对直径端点与两个距离数组，再扫描一遍取答案：
ans = 直径长 + max_u min(d(u, A), d(u, B))
复杂度和 C++ 版一致，都是 O(N)，但 Python 常数较大，在 N = 2e5 的随机树上
约 1.4 s，会超出本题时限，因此只作为阅读对照，正式主解是 main.cpp。
"""
import sys
def main():
data = sys.stdin.buffer
n, edges = map(int, data.readline().split())
graph = [[] for _ in range(n + 1)] # graph[u] 是 (邻居, 边权) 的列表
for _ in range(edges):
u, v, weight = map(int, data.readline().split())
graph[u].append((v, weight))
graph[v].append((u, weight))
def distances(start):
"""从 start 出发遍历整棵树，返回到各点的距离数组。"""
distance = [-1] * (n + 1) # 用 -1 当"未访问"标记：边权可以为 0
distance[start] = 0
order = [start]
for node in order: # order 一边当队列用，一边记录遍历顺序
for neighbor, weight in graph[node]:
if distance[neighbor] == -1:
distance[neighbor] = distance[node] + weight
order.append(neighbor)
return distance
from_one = distances(1)
# 两次最远点搜索求出一对直径端点 first 和 second。
first = max(range(1, n + 1), key=from_one.__getitem__)
from_first = distances(first)
second = max(range(1, n + 1), key=from_first.__getitem__)
from_second = distances(second)
# 答案是「直径长 + 到两端较近距离的最大值」。
best_extra = max(
min(da, db) for da, db in zip(from_first[1:], from_second[1:])
)
print(from_first[second] + best_extra)
if __name__ == "__main__":
main()Python 版在本机 main.cpp.
复杂度
- 时间: 三次遍历各
, 最后一次扫描 , 共 . - 空间: 邻接表与两个距离数组,
.
解法二：树形换根 DP（枚举汇合中心）
思路
如果不想证明“两朋友必为直径端点”，有没有更直接暴力的树形结构做法？
答案是：直接枚举三叉臂的汇合中心点
回忆第一步中的物理拆解：
无论三点选在哪里，它们必定交汇于唯一的中心点
因此，如果我们将
由于我们需要考察每个节点作为中心点
- 第一次 DFS（自底向上）：
维护每个节点
在其子树内部向下走出的前三长链： down[u][0..2]，并记录取到这些最值时的直接子节点编号best_child[u][0..2]。 - 第二次 DFS（自顶向下换根）：
将从父节点往上走能走到的最长链
up[u]传递给各个子节点。在每个节点处，汇总向下延伸的前三长链和向上延伸的 up[u]链，挑出全局前三长的独立分支，用 更新全局最大值。
这种做法的好处是：完全不需要树的直径性质，也不需要证明任何贪心结论，完全由树的拓扑结构自然驱动。
代码
/**
* 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-26 20:37
* update_at: 2026-10-26 20:37
*/
// main2.cpp：换根 DP（二次扫描与换根）解法
// 核心思路：枚举三叉臂的汇合中心点 m，在 m 处向不同子树拉出前三长链 l1 >= l2 >= l3
// 最大路程为一条主干道(走一次)加一条支链折返(走两次)：l1 + 2 * l2 + l3
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 200005;
struct Edge {
int to;
ll w;
};
int n, m;
vector<Edge> g[MAXN];
// down[u][0..2]：节点 u 在其以 1 为根的子树内，向不同子树走出的最长、次长、第三长链长度
ll down[MAXN][3];
// best_child[u][0..2]：对应链走入的具体子节点编号
int best_child[MAXN][3];
// up[u]：从 u 沿着父亲方向向外能走的最长链长度
ll up_chain[MAXN];
ll ans = 0;
void insert_down(int u, ll val, int child) {
if (val > down[u][0]) {
down[u][2] = down[u][1];
best_child[u][2] = best_child[u][1];
down[u][1] = down[u][0];
best_child[u][1] = best_child[u][0];
down[u][0] = val;
best_child[u][0] = child;
} else if (val > down[u][1]) {
down[u][2] = down[u][1];
best_child[u][2] = best_child[u][1];
down[u][1] = val;
best_child[u][1] = child;
} else if (val > down[u][2]) {
down[u][2] = val;
best_child[u][2] = child;
}
}
// 第一次 DFS：自底向上统计子树内的最长、次长、第三长链
void dfs1(int u, int fa) {
for (auto &e : g[u]) {
int v = e.to;
if (v == fa) continue;
dfs1(v, u);
insert_down(u, down[v][0] + e.w, v);
}
}
// 第二次 DFS：自顶向下传递 up 链，并在每个点汇聚所有方向的前三长链更新全局答案
void dfs2(int u, int fa) {
// 收集节点 u 向外延伸的所有独立分支（向下最多 3 条，向上 1 条）
vector<ll> chains;
for (int i = 0; i < 3; i++) {
if (down[u][i] > 0) chains.push_back(down[u][i]);
}
if (up_chain[u] > 0) chains.push_back(up_chain[u]);
sort(chains.begin(), chains.end(), greater<ll>());
// 若至少有三条分支，第二长链翻倍：l1 + 2*l2 + l3
// 若只有两条分支，第三条视作长度 0：l1 + 2*l2
// 若只有一条分支，翻倍也是合法的退化情况
if (chains.size() >= 3) {
ans = max(ans, chains[0] + 2 * chains[1] + chains[2]);
} else if (chains.size() == 2) {
ans = max(ans, chains[0] + 2 * chains[1]);
} else if (chains.size() == 1) {
ans = max(ans, chains[0]);
}
for (auto &e : g[u]) {
int v = e.to;
if (v == fa) continue;
// 计算给子节点 v 传递的 up 链：u 的除 v 以外的最长分支 + e.w
ll max_other = up_chain[u];
if (best_child[u][0] != v) {
max_other = max(max_other, down[u][0]);
} else {
max_other = max(max_other, down[u][1]);
}
up_chain[v] = max_other + e.w;
dfs2(v, u);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (!(cin >> n >> m)) return 0;
for (int i = 0; i < m; i++) {
int u, v;
ll w;
cin >> u >> v >> w;
g[u].push_back({v, w});
g[v].push_back({u, w});
}
dfs1(1, 0);
dfs2(1, 0);
cout << ans << "\n";
return 0;
}复杂度
- 时间复杂度：两次 DFS 各遍历整棵树一次，每个节点只做常数大小的前三链合并与排序，总时间复杂度为严格的
。 - 空间复杂度：存储邻接表与前三长链数组，总空间复杂度为
。
复杂度对比
| 方案 | 维护结构 | 时间 | 空间 | 相对特点 |
|---|---|---|---|---|
main.cpp / main.py（解法一） |
三次 BFS + 两个距离数组 | 依赖直径性质，代码最短 | ||
main2.cpp（解法二） |
两次 DFS + 每个节点前三长链 | 不依赖直径，常数略大 |
两者的复杂度同阶，差别在常数与证明负担：解法一只做三次遍历，但必须先证明「朋友取直径端点」；解法二要做两次 DFS 并在每个节点维护前三长链（含换根时的比较与更新），但跳过了全部几何论证。因此追求代码简短选解法一，追求「不需要任何结论」选解法二。
总结
本题提供了两种完全不同视角的
- 解法一（主解：直径端点贪心）：
通过三叉臂展开发现物理本质是「主干道直达走一次 + 侧向支链折返走两次」，即
。再把 改写成「三个两两距离中的最小值 + 最大值」，分别封顶： （直径最长）， （三点必有两点同侧，同侧两点的距离不超过较远者到直径端点的距离）。两个上界相加即 ，选两个朋友为直径两极正好取满。代码仅需三次简单的 BFS/DFS，非常简洁。 - 解法二（进阶：树形换根 DP）：
完全跳过对“直径端点”的推导证明，直接枚举三叉臂的汇合中心点
。通过树形二次扫描与换根 DP 维护向外延伸的前三长链 ，以 结算局部最优。思维直接、不依赖特殊图论引理。
实现细节注意点：
- 边权可以为
，解法一的距离数组要用 而不是 当未访问标记； - 答案量级最大可达
，必须用 64 位整数（C++ 中使用 long long）。
图示解析
这张图把整道题的推导与解法结构串起来：
暴力枚举 (brute.cpp)
枚举三点 (C, A, B), 每组跑遍历求距离
f = min(d(C,A), d(C,B)) + d(A,B) O(N^4)
|
| 瓶颈: 三点组合太多，如何降维？
v
物理拆解: 三叉臂中心视角
三点必在唯一的中心点 m 汇合，臂长分别为 a, b, c (设 b <= c)
总路程 = (a + c) [主干道走一次] + 2b [侧向支链走折返]
|
+-----------------------------------+
| |
v v
【路线 A】全树极值放缩 (解法一: main.cpp) 【路线 B】换根 DP (解法二: main2.cpp)
f = P_min + (另一加数) <= P_min + P_max 以 m 为根，找向外前三长链:
1. P_max <= 直径长 D l1 >= l2 >= l3
2. P_min <= max_u h(u) (三点必有两点同侧) Ans_m = l1 + 2 * l2 + l3
=> 上界 D + max_u h(u)
=> 朋友直接选直径两端 A, B 取满天花板! 树形 DP + 二次扫描换根全局更新
=> 3 次 BFS 线性扫描 (O(N)) => 两次 DFS 遍历即可 (O(N))