GESP 题解库 / 8 级题解 / [GESP202406 八级] 最远点对 · 第 16 / 24 题
GESP202406 八级 · P10725 · 困难

树上最远异色点对

分别求出黑点集与白点集的直径端点,再在 4 种跨集合组合里取最大。

🌲
n ≤ 10⁵
树的结点数
⚫
黑白两色
每个结点非黑即白
⚡
O(n)
只要 5 次迭代 BFS
🎯
两类点集各求直径
核心引理
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

小杨有一棵包含 n 个结点的树,树上的任意一个结点要么是白色,要么是黑色。小杨想知道相距最远的一对不同颜色结点的距离是多少(两点距离 = 它们之间路径上的边数)。

输入格式:第一行包含一个正整数 n,代表树的结点数。第二行包含 n 个非负整数 a₁, a₂, …, aₙ(对所有的 1 ≤ i ≤ n 均有 aᵢ 等于 0 或 1):aᵢ = 0 表示结点 i 为白色,aᵢ = 1 表示结点 i 为黑色。之后 n − 1 行,每行包含两个正整数 xᵢ, yᵢ,代表存在一条连接结点 xᵢ 和 yᵢ 的边。保证输入的树中存在不同颜色的点。

输出格式:输出一个整数,代表相距最远的一对不同颜色结点的距离。

输入输出样例

样例内容
输入 #15
0 1 0 1 0
1 2
1 3
3 4
3 5
输出 #13
样例解释相距最远的一对不同颜色结点为结点 2 和结点 5,路径为 2 → 1 → 3 → 5,共 3 条边
💡
人话翻译:把所有"一黑一白"的结点对都看一遍,找距离最大的那一对。
最容易想到的是"求整棵树的直径",但这不保险——直径的两个端点可能同色。
正确的转念是:黑点集自己有一个"直径",白点集自己也有一个"直径"。先把这两个直径的端点求出来,记为黑端的 b₁, b₂ 与白端的 w₁, w₂,
那么答案一定等于 dist(b₁, w₁)、dist(b₁, w₂)、dist(b₂, w₁)、dist(b₂, w₂) 这四个数里的最大值。
求直径端点的标准套路是"两次 BFS":从任一黑点出发找到最远的黑点 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

需要解决的问题

02
思维导图
整理解题思路的全貌
⚫⚪ 两个点集各求直径,再跨集合比较
🧠 问题转化
要的是"一对异色结点"的最远距离
即 max over 黑 b、白 w 的 dist(b, w)
不能只看整棵树的直径
整树直径两端可能同色
📐 核心引理
对任意 v,离 v 最远的 S 中点
必是 diam(S) 的两个端点之一
证明靠"直径两端"的距离不等式
于是只需比较 4 个固定组合
🔁 具体步骤
任一黑点 BFS → 黑集端点 b₁
从 b₁ BFS → 黑集端点 b₂
任一白点 BFS → 白集端点 w₁
从 w₁ BFS → 白集端点 w₂
答案 = 4 个跨集合距离的最大值
⚠️ 易错点
递归 DFS 在 n = 10⁵ 的链上爆栈
误用整树直径(端点可能同色)
只比较 dist(b₁, w₁) 一个组合
某个颜色只有 1 个点时乱特判
03
样例手算推导
样例 1 手算 + "引理"为什么成立

🧮 样例 1 手算:先各自求直径,再跨集合比较

样例树有 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
1
第 1 步:求黑点集 B = {2, 4} 的直径端点

从任一黑点出发,比如从 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

2
第 2 步:求白点集 W = {1, 3, 5} 的直径端点

从任一白点出发,比如从 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

3
第 3 步:4 个跨集合组合各算一次距离

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

4
第 4 步:与题面样例对照

样例输出是 3

题面给出的"相距最远的一对"正是结点 2 与结点 5

恰好就是我们算出的 b₁ = 2 与 w₂ = 5

说明"端点组合"确实覆盖了真正的最优解

✅ 答案 3

🔑
只算 4 个组合为什么就够?因为引理告诉我们两件事:① 离任意黑点 b 最远的白点,只能是 w₁ 或 w₂;② 在所有黑点里,离固定白点 v 最远的黑点,只能是 b₁ 或 b₂。把 ① 用在"答案那一对里的黑点"上、把 ② 用在"答案那一对里的白点"上,就能推出全局最优解一定落在 4 个端点的组合里。

🔎 引理证明 + 一个"整树直径会算错"的反例

反例:整棵树的直径可能两端同色

取一条 6 个结点的链 1–2–3–4–5–6,颜色为 1 = 黑、2 ~ 5 = 白、6 = 黑。

结点123456
颜色⚫ 黑⚪ 白⚪ 白⚪ 白⚪ 白⚫ 黑

整棵树的直径是 dist(1, 6) = 5,可这两个端点都是黑点——它不是本题答案。真正的答案是 dist(1, 5) = dist(2, 6) = 4(一黑一白)。只看整树直径会输出 5,直接错。

1
引理:对任意结点 v,点集 S 中离 v 最远的点必是 diam(S) 的端点之一

设 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 有多远"

2
分三种方向估计 dist(p, c)

① 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) 控住

3
于是"离 v 最远的点"可以在 {a, 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,这个上界是能取到的

✅ 引理成立

4
套到本题:从两点集引理到 4 个组合

取 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₂) }

⚠️
把两件事分清:
· "整棵树里最远的点对"(树的直径)——不要求异色;
· "一黑一白里最远的点对"(本题)——必须在异色点对里找,它的值可能小于树的直径,也可能恰好相等。
所以照搬"两次 BFS 求直径"的模板,只要忘了颜色这个限制,就会在"直径两端同色"的数据上翻车。
04
解法对比
两点集各求直径 vs 只求整树直径 / 逐对枚举

⚔️ 解法对比

🟢 黑白点集各求直径 + 5 次 BFS(推荐) 推荐

黑点集求直径端点 b₁, b₂,白点集求直径端点 w₁, w₂,再比较 4 个跨集合距离

  • 时间 O(n),共 5 次 BFS
  • n = 10⁵ 时约 5 × 10⁵ 步
  • 代码约 60 行
  • 迭代 BFS,不会爆栈
💡
正确性来源:"离 v 最远的 S 中点必是 diam(S) 的端点"把 |B| × |W| 种组合压缩到 4 种;而这 4 个数又都对应真实的异色点对,"上界能取到 + 每个候选都合法",两头都站得住。

🟠 只求整棵树的直径

两次 BFS 找出树的直径端点,直接输出直径长度

  • 时间 O(n),只要 2 次 BFS
  • 代码最短,但结论是错的
  • 样例 1 能过(恰好两端异色)
  • 一遇到"直径两端同色"就挂
⚠️
它为什么会挂:题目限定"一对不同颜色的结点",而整树直径的两端完全可能同色。
反例(链 1–2–3–4–5–6,1、6 为黑,2 ~ 5 为白):整树直径 5 的两端都是黑点,正确答案是 4。

📈 性能对比

方案复杂度结论
两点集各求直径 + 5 次 BFSO(n) ≈ 5 × 10⁵✅ 正确,推荐
只求整树直径O(n)(2 次 BFS)❌ 端点同色即挂
枚举异色点对 + 每对跑 BFSO(|B| × |W| × n),最坏 10¹⁵❌ 完全不可行
枚举异色点对 + LCA 求距离O(n log n) + O(|B| × |W|)❌ |B| × |W| 可达 2.5 × 10⁹
05
算法流程图
求两个点集直径 + 4 组合取最大
开始读入 n、颜色 aᵢ 与 n − 1 条边,建邻接表按颜色把结点分成黑集 B 与白集 W黑集直径:任一黑点 BFS → b₁,再从 b₁ BFS → b₂白集直径:任一白点 BFS → w₁,再从 w₁ BFS → w₂枚举 4 个跨集合组合,各求一次距离这个距离 > ans 吗?是 ✓ans = 该距离否 ✗ans 不变4 个组合都比完了吗?输出 ans(最远异色点对的距离)换下一组点对
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🌲 最远异色点对计算器

第一行 n;第二行 n 个 0/1(0 白、1 黑);随后 n − 1 行边。程序会求出黑白两个点集的直径端点,比较 4 个跨集合距离,并顺带给出整棵树直径作对照。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码(两次 BFS 求点集直径 + 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;
}
🔑
三个要点:① 距离计算用迭代 BFS(手写队列),递归 DFS 在 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 个数里
⚠️
五个坑:① 用递归 DFS 求距离(n = 10⁵ 的链会栈溢出);② 照搬"整树直径"(端点可能同色,反例会输出 5 而正确答案是 4);③ 只比较 dist(b₁, w₁) 一个组合(漏解);④ 某个颜色只有 1 个点时特意特判输出 0(其实不需要特判,该点集直径为 0、两个端点同一个点,取 max 自然正确);⑤ 邻接表只开了 n 个位置却按 1…n 编号存点(要开 n + 1)。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
5
0 1 0 1 0
1 2
1 3
3 4
3 5
3题面样例 1:最远异色点对是结点 2 与 5
2
0 1
1 2
1最小规模:一黑一白,直接相连
6
1 0 0 0 0 1
1 2
2 3
3 4
4 5
5 6
4整树直径 5 落在两个黑点之间,只能用异色的 4
4
0 1 1 1
1 2
1 3
1 4
1白点只有 1 个(菊花中心),白集直径为 0
6
0 0 0 1 0 0
1 2
2 3
3 4
4 5
5 6
3黑点只有 1 个,答案是离它最远的白点
5
1 1 0 0 0
1 2
2 3
3 4
4 5
4一条链:黑点 1、2 与白点 5 相距 4
✅
自查清单:① 用的是迭代 BFS 吗?② 黑、白两个点集都求了直径端点吗?③ 比的是 4 个跨集合组合吗?④ 有没有偷偷用"整树直径"来偷懒?

🚨 易错点清单

⚠️
递归 DFS 爆栈:n = 10⁵ 且树退化成链时递归深度达到 10⁵,必须写手写队列的迭代 BFS。
⚠️
误用整树直径:整树直径的两端可能同色,链 1–2–3–4–5–6(1、6 黑,其余白)会算出 5,正确答案是 4。
⚠️
只比较一个组合:必须比较 dist(b₁,w₁)、dist(b₁,w₂)、dist(b₂,w₁)、dist(b₂,w₂) 四个,只算其中一两个会漏掉最优解。
⚠️
某个颜色只有 1 个点:该点集的直径是 0、两个端点是同一个点,4 个组合里出现重复项是正常的,不要特判成 0 或 −1。
⚠️
下标与数组大小:结点编号是 1…n,邻接表与距离数组都要开到 n + 1。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(n)
空间复杂度
O(n)
BFS 次数
5 次
最大运算量
约 5 × 10⁵ 步

时间怎么算的?

空间都用在哪?

邻接表存 2(n − 1) 条边,约 O(n);每个距离数组 O(n),同时最多保留 3 个(db1、db2、dw1);BFS 的队列 O(n)。总体只有几 MB,远低于 256 MB。

✅ n = 10⁵ 时总运算量约 5 × 10⁵ 次访问,1 秒时限下轻松通过——这正是本题官方解法的复杂度。关键是"5 次线性 BFS"代替了"平方级的点对枚举"。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// ① 迭代 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)

// ⑤ 提醒:"整棵树直径"与"异色点对最远距离"是两回事
//    只有当直径两端恰好异色时两者才相等

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
迭代 BFS5 次 BFS 算出所有需要的树上距离无权图最短路、树上距离、树的直径
两次 BFS 求直径在"黑点集""白点集"内部各求一次最远点对树的直径、点集直径、带限制的最远点对
引理压缩枚举把 |B| × |W| 种组合压到 2 × 2 = 4 种两集合间的最值问题、直径端点的性质类题目
LCA 求距离如果想批量算 dist(bᵢ, wⱼ),可换成 LCA需要多次询问树上两点距离的题
🌟
思考题:如果颜色变成 3 种(黑、白、灰),要你求"异色点对的最远距离"该怎么办?(提示:引理对每个点集单独成立,所以先求出三种颜色各自的直径端点,一共 6 个点,再枚举"端点对且两端颜色不同"的若干组合取最大即可;端点数量从 4 个变成 6 个,枚举量仍然是常数。)