分别求出黑点集与白点集的直径端点,再在 4 种跨集合组合里取最大。
小杨有一棵包含 n 个结点的树,树上的任意一个结点要么是白色,要么是黑色。小杨想知道相距最远的一对不同颜色结点的距离是多少(两点距离 = 它们之间路径上的边数)。
输入格式:第一行包含一个正整数 n,代表树的结点数。第二行包含 n 个非负整数 a₁, a₂, …, aₙ(对所有的 1 ≤ i ≤ n 均有 aᵢ 等于 0 或 1):aᵢ = 0 表示结点 i 为白色,aᵢ = 1 表示结点 i 为黑色。之后 n − 1 行,每行包含两个正整数 xᵢ, yᵢ,代表存在一条连接结点 xᵢ 和 yᵢ 的边。保证输入的树中存在不同颜色的点。
输出格式:输出一个整数,代表相距最远的一对不同颜色结点的距离。
| 样例 | 内容 |
|---|---|
| 输入 #1 | 5 |
| 输出 #1 | 3 |
| 样例解释 | 相距最远的一对不同颜色结点为结点 2 和结点 5,路径为 2 → 1 → 3 → 5,共 3 条边 |
b₁, b₂ 与白端的 w₁, w₂,dist(b₁, w₁)、dist(b₁, w₂)、dist(b₂, w₁)、dist(b₂, w₂) 这四个数里的最大值。b₁,再从 b₁ 出发找到最远的黑点 b₂;白点同理。全程 5 次 BFS,复杂度 O(n)。树的直径两个点集各求直径跨集合最远点对迭代 BFS 防爆栈引理压缩枚举
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 n;第二行 n 个 0/1;随后 n − 1 行边 |
| 输出 | 一个整数:最远异色点对的距离(边数) |
| 数据范围 | 1 ≤ n ≤ 10⁵,0 ≤ aᵢ ≤ 1 |
| 保证 | 树中同时存在黑点与白点(答案至少为 1) |
| 子任务 | 30 分:树是一条链;30 分:n ≤ 10³;40 分:n ≤ 10⁵(捆绑测试) |
| 时限 | 1 秒 / 256 MB |
v,点集 S 中离 v 最远的点一定是 S 的直径端点之一。把 v 取成黑点、S 取成白点集,再把角色对调一次,就能把 |B| × |W| 种组合压缩成 2 × 2 = 4 种n = 10⁵ 的链会让递归 DFS 的深度达到 10⁵,在栈上直接爆掉,所以距离计算要用手写队列的迭代 BFS样例树有 5 个结点:黑点是 2 与 4,白点是 1、3、5;四条边为 1–2、1–3、3–4、3–5。整棵树长这样:结点 1 连着 2 和 3,结点 3 再连着 4 和 5。
| 结点 | 颜色 | 与谁相邻 |
|---|---|---|
| 1 | ⚪ 白 | 2, 3 |
| 2 | ⚫ 黑 | 1 |
| 3 | ⚪ 白 | 1, 4, 5 |
| 4 | ⚫ 黑 | 3 |
| 5 | ⚪ 白 | 3 |
从任一黑点出发,比如从 2 出发 BFS
到 2 的距离:dist(2,2) = 0,dist(2,4) = 3(2 → 1 → 3 → 4)
最远的黑点是 4 ⟹ b₁ = 2、b₂ = 4(先取 2 再取 4)
黑集只有两个点,所以黑集直径就是 dist(2, 4) = 3
黑集直径 = 3,端点 b₁ = 2、b₂ = 4
从任一白点出发,比如从 1 出发 BFS
dist(1, 3) = 1(边 1–3)
dist(1, 5) = 2(路径 1 → 3 → 5)
最远的白点是 5 ⟹ w₁ = 1、w₂ = 5
再核对一遍:dist(3, 5) = 1,都比 dist(1, 5) 小
白集直径 = 2,端点 w₁ = 1、w₂ = 5
dist(b₁, w₁) = dist(2, 1) = 1(直接走边 1–2)
dist(b₁, w₂) = dist(2, 5) = 3(2 → 1 → 3 → 5)
dist(b₂, w₁) = dist(4, 1) = 2(4 → 3 → 1)
dist(b₂, w₂) = dist(4, 5) = 2(4 → 3 → 5)
四个数里最大的是 3
样例输出是 3
题面给出的"相距最远的一对"正是结点 2 与结点 5
恰好就是我们算出的 b₁ = 2 与 w₂ = 5
说明"端点组合"确实覆盖了真正的最优解
✅ 答案 3
b 最远的白点,只能是 w₁ 或 w₂;② 在所有黑点里,离固定白点 v 最远的黑点,只能是 b₁ 或 b₂。把 ① 用在"答案那一对里的黑点"上、把 ② 用在"答案那一对里的白点"上,就能推出全局最优解一定落在 4 个端点的组合里。取一条 6 个结点的链 1–2–3–4–5–6,颜色为 1 = 黑、2 ~ 5 = 白、6 = 黑。
| 结点 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 颜色 | ⚫ 黑 | ⚪ 白 | ⚪ 白 | ⚪ 白 | ⚪ 白 | ⚫ 黑 |
整棵树的直径是 dist(1, 6) = 5,可这两个端点都是黑点——它不是本题答案。真正的答案是 dist(1, 5) = dist(2, 6) = 4(一黑一白)。只看整树直径会输出 5,直接错。
设 a、b 是点集 S 的直径端点(dist(a, b) 是 S 内两点的最大距离)
设 c 是 S 中离 v 最远的点(若有多个,任取一个)
记 p 为"v、a、b 三条路径分开的那个分叉点"(树上唯一)
于是 dist(v, c) = dist(v, p) + dist(p, c),只差把 dist(p, c) 估住
把问题压缩成"c 离 p 有多远"
① c 在 p 的 a 方向:dist(b, c) = dist(b, p) + dist(p, c) ≤ dist(a, b)
⟹ dist(p, c) ≤ dist(p, a)
② c 在 p 的 b 方向:dist(a, c) = dist(a, p) + dist(p, c) ≤ dist(a, b)
⟹ dist(p, c) ≤ dist(p, b)
③ c 在 p 的 v 方向:同样由 dist(a, c) ≤ dist(a, b) 得 dist(p, c) ≤ dist(p, b)
两个不等式都来自"a、b 是 S 的直径"这一事实
三种情况下 dist(p, c) 都被 dist(p, a) 或 dist(p, b) 控住
情况 ①:dist(v, c) ≤ dist(v, p) + dist(p, a) = dist(v, a)
情况 ②③:p 在 v → b 的路径上,dist(v, c) ≤ dist(v, p) + dist(p, b) = dist(v, b)
所以 dist(v, c) 不超过 dist(v, a) 与 dist(v, b) 的较大者
而 a、b 本身属于 S,这个上界是能取到的
✅ 引理成立
取 S = 白点集、v = 任意黑点 b:离 b 最远的白点是 w₁ 或 w₂
所以答案 = max over 黑点 b 的 max(dist(b, w₁), dist(b, w₂))
再取 S = 黑点集、v = w₁:离 w₁ 最远的黑点是 b₁ 或 b₂;w₂ 同理
两层 max 一合并 ⟹ 只需比较 4 个跨集合距离
✅ 答案 = max{ dist(b₁,w₁), dist(b₁,w₂), dist(b₂,w₁), dist(b₂,w₂) }
黑点集求直径端点 b₁, b₂,白点集求直径端点 w₁, w₂,再比较 4 个跨集合距离
|B| × |W| 种组合压缩到 4 种;而这 4 个数又都对应真实的异色点对,"上界能取到 + 每个候选都合法",两头都站得住。两次 BFS 找出树的直径端点,直接输出直径长度
| 方案 | 复杂度 | 结论 |
|---|---|---|
| 两点集各求直径 + 5 次 BFS | O(n) ≈ 5 × 10⁵ | ✅ 正确,推荐 |
| 只求整树直径 | O(n)(2 次 BFS) | ❌ 端点同色即挂 |
| 枚举异色点对 + 每对跑 BFS | O(|B| × |W| × n),最坏 10¹⁵ | ❌ 完全不可行 |
| 枚举异色点对 + LCA 求距离 | O(n log n) + O(|B| × |W|) | ❌ |B| × |W| 可达 2.5 × 10⁹ |
第一行 n;第二行 n 个 0/1(0 白、1 黑);随后 n − 1 行边。程序会求出黑白两个点集的直径端点,比较 4 个跨集合距离,并顺带给出整棵树直径作对照。
点按钮开始 →
#include <bits/stdc++.h> using namespace std; int n; vector<int> g[100005]; // 邻接表 int col[100005]; // 0 = 白,1 = 黑 vector<int> B, W; // 黑点集、白点集 // 迭代 BFS:返回 src 到所有结点的距离(-1 表示不可达) vector<int> bfs(int src) { vector<int> d(n + 1, -1); vector<int> q(n + 1); // 手写队列,绝不递归,防爆栈 int head = 0, tail = 0; d[src] = 0; q[tail++] = src; while (head < tail) { int x = q[head++]; for (int i = 0; i < (int)g[x].size(); i++) { int y = g[x][i]; if (d[y] == -1) { d[y] = d[x] + 1; q[tail++] = y; } } } return d; } // 在点集 cand 中找离 src 最远的点,并通过 out 传出这组距离 int farthestFrom(int src, const vector<int>& cand, vector<int>& out) { out = bfs(src); int best = cand[0]; for (int i = 1; i < (int)cand.size(); i++) if (out[cand[i]] > out[best]) best = cand[i]; return best; // 引理保证:它一定是 cand 的直径端点 } int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &col[i]); if (col[i] == 1) B.push_back(i); else W.push_back(i); } for (int i = 1; i < n; i++) { int x, y; scanf("%d %d", &x, &y); g[x].push_back(y); g[y].push_back(x); } vector<int> tmp, db1, dw1; // 1) 黑点集直径端点 b1、b2(两次 BFS) int b1 = farthestFrom(B[0], B, tmp); // tmp 只用来挑出端点 int b2 = farthestFrom(b1, B, db1); // db1[u] = dist(b1, u) vector<int> db2 = bfs(b2); // db2[u] = dist(b2, u) // 2) 白点集直径端点 w1、w2(两次 BFS) int w1 = farthestFrom(W[0], W, tmp); // 复用 tmp int w2 = farthestFrom(w1, W, dw1); // dw1[u] = dist(w1, u) // 3) 4 个跨集合组合取最大 int ans = 0; ans = max(ans, db1[w1]); // dist(b1, w1) ans = max(ans, db1[w2]); // dist(b1, w2) ans = max(ans, db2[w1]); // dist(b2, w1) ans = max(ans, db2[w2]); // dist(b2, w2) printf("%d\n", ans); return 0; }
n = 10⁵ 的链上必然爆栈;② 求直径只需要两次 BFS:任取一点找最远点得一个端点,再从该端点找最远点得另一个端点;③ 最后比较 4 个跨集合组合,少比一个都可能漏掉最优解。| 代码 | 作用 | 为什么这样写 |
|---|---|---|
vector<int> q(n + 1); head = tail = 0; | 手写队列 | 迭代 BFS,深度不占栈 |
int b1 = farthestFrom(B[0], B, db1); | 黑集第一个端点 | 从任一黑点出发,最远的黑点必是直径端点 |
int b2 = farthestFrom(b1, B, db1); | 黑集第二个端点 | 再从 b1 走一次就锁定直径;db1 顺便给出全场距离 |
vector<int> db2 = bfs(b2); | 第 5 次 BFS | 补上 dist(b₂, w₁)、dist(b₂, w₂) 两个数 |
if (col[i] == 1) B.push_back(i); | 分色 | 后续所有"最远点"都只在同色集合里找 |
max(max(db1[w1], db1[w2]), max(db2[w1], db2[w2])) | 4 组合取最大 | 引理保证答案就在这 4 个数里 |
n = 10⁵ 的链会栈溢出);② 照搬"整树直径"(端点可能同色,反例会输出 5 而正确答案是 4);③ 只比较 dist(b₁, w₁) 一个组合(漏解);④ 某个颜色只有 1 个点时特意特判输出 0(其实不需要特判,该点集直径为 0、两个端点同一个点,取 max 自然正确);⑤ 邻接表只开了 n 个位置却按 1…n 编号存点(要开 n + 1)。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
5 | 3 | 题面样例 1:最远异色点对是结点 2 与 5 |
2 | 1 | 最小规模:一黑一白,直接相连 |
6 | 4 | 整树直径 5 落在两个黑点之间,只能用异色的 4 |
4 | 1 | 白点只有 1 个(菊花中心),白集直径为 0 |
6 | 3 | 黑点只有 1 个,答案是离它最远的白点 |
5 | 4 | 一条链:黑点 1、2 与白点 5 相距 4 |
n = 10⁵ 且树退化成链时递归深度达到 10⁵,必须写手写队列的迭代 BFS。dist(b₁,w₁)、dist(b₁,w₂)、dist(b₂,w₁)、dist(b₂,w₂) 四个,只算其中一两个会漏掉最优解。1…n,邻接表与距离数组都要开到 n + 1。邻接表存 2(n − 1) 条边,约 O(n);每个距离数组 O(n),同时最多保留 3 个(db1、db2、dw1);BFS 的队列 O(n)。总体只有几 MB,远低于 256 MB。
✅ n = 10⁵ 时总运算量约 5 × 10⁵ 次访问,1 秒时限下轻松通过——这正是本题官方解法的复杂度。关键是"5 次线性 BFS"代替了"平方级的点对枚举"。
// ① 迭代 BFS 求树上距离(防爆栈,通用) vector<int> bfs(int src) { vector<int> d(n + 1, -1), q(n + 1); int head = 0, tail = 0; d[src] = 0; q[tail++] = src; while (head < tail) { int x = q[head++]; for (int i = 0; i < (int)g[x].size(); i++) { int y = g[x][i]; if (d[y] == -1) { d[y] = d[x] + 1; q[tail++] = y; } } } return d; } // ② 点集直径模板:两次 BFS 拿到两个端点,并给出两端的距离数组 // cand 为点集;返回 {a, b};dA[u] = dist(a, u),dB[u] = dist(b, u) pair<int,int> diameterOf(const vector<int>& cand, vector<int>& dA, vector<int>& dB) { dA = bfs(cand[0]); int a = cand[0]; for (int i = 1; i < (int)cand.size(); i++) if (dA[cand[i]] > dA[a]) a = cand[i]; // 第一个端点 dB = bfs(a); int b = a; for (int i = 1; i < (int)cand.size(); i++) if (dB[cand[i]] > dB[b]) b = cand[i]; // 第二个端点 dA = dB; // dA 变成 dist(a, ·) return make_pair(a, b); } // ③ 两个集合之间的最远点对:只需比较 4 种端点组合 // ans = max{ dist(b1,w1), dist(b1,w2), dist(b2,w1), dist(b2,w2) } // ④ 若要批量询问两点距离,BFS 换成 LCA + 深度 // dist(u, v) = dep[u] + dep[v] - 2 * dep[lca(u, v)] // O(n log n) 预处理后每次 O(log n) // ⑤ 提醒:"整棵树直径"与"异色点对最远距离"是两回事 // 只有当直径两端恰好异色时两者才相等
把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。
| 能力点 | 本题怎么用 | 还能迁移到 |
|---|---|---|
| 迭代 BFS | 5 次 BFS 算出所有需要的树上距离 | 无权图最短路、树上距离、树的直径 |
| 两次 BFS 求直径 | 在"黑点集""白点集"内部各求一次最远点对 | 树的直径、点集直径、带限制的最远点对 |
| 引理压缩枚举 | 把 |B| × |W| 种组合压到 2 × 2 = 4 种 | 两集合间的最值问题、直径端点的性质类题目 |
| LCA 求距离 | 如果想批量算 dist(bᵢ, wⱼ),可换成 LCA | 需要多次询问树上两点距离的题 |