: 最远点对)
2024年6月GESP真题及题解(C++八级): 最远点对
题目描述
小杨有一棵包含n nn个节点的树，这棵树上的任意一个节点要么是白色，要么是黑色。
小杨想知道相距最远的一对不同颜色节点的距离是多少。
输入格式
第一行包含一个正整数n nn，代表树的节点数。
第二行包含n nn个非负整数a 1 , a 2 , ⋯ , a n a_1,a_2,\cdots,a_na1,a2,⋯,an（对于所有的1 ≤ i ≤ n 1\le i\le n1≤i≤n，均有a i a_iai等于0 00或1 11），其中如果a i = 0 a_i=0ai=0，则节点i ii的颜色为白色；如果a i = 1 a_i=1ai=1，则节点i ii的颜色为黑色。
之后( n − 1 ) (n-1)(n−1)行，每行包含两个正整数x i , y i x_i,y_ixi,yi，代表存在一条连接节点x i x_ixi和y i y_iyi的边。
保证输入的树中存在不同颜色的点。
输出格式
输出一个整数，代表相距最远的一对不同颜色节点的距离。
输入输出样例 1
输入 1
5 0 1 0 1 0 1 2 1 3 3 4 3 5输出 1
3说明/提示
样例解释
相距最远的不同颜色的一对节点为节点2 22和5 55。
数据范围
| 子任务编号 | 得分 | n nn | a i a_iai | 特殊条件 |
|---|---|---|---|---|
| 1 11 | 30 3030 | ≤ 10 5 \le 10^5≤105 | 0 ≤ a i ≤ 1 0\le a_i\le 10≤ai≤1 | 树的形态为一条链 |
| 2 22 | 30 3030 | ≤ 10 3 \le 10^3≤103 | 0 ≤ a i ≤ 1 0\le a_i\le 10≤ai≤1 | |
| 3 33 | 40 4040 | ≤ 10 5 \le 10^5≤105 | 0 ≤ a i ≤ 1 0\le a_i\le 10≤ai≤1 |
对于全部数据，保证有1 ≤ n ≤ 10 5 1\le n\le 10^51≤n≤105，0 ≤ a i ≤ 1 0\le a_i\le 10≤ai≤1。
思路分析
理解问题本质：在树上找到距离最远的两个异色节点，距离定义为节点间路径的边数。
暴力解法不可行：直接枚举所有异色节点对是 O(n²) 的，n ≤ 10⁵ 时不可行。
高效解法思路：
- 树的直径通常可以通过两次 BFS/DFS 找到最远点对
- 但这里要求是不同颜色的节点对
- 关键观察：最远异色节点对一定包含某个颜色的最远点之一
算法设计：
- 对于每种颜色，找到距离该颜色所有节点最远的节点
- 从白色节点中找到距离所有黑色节点最远的点
- 从黑色节点中找到距离所有白色节点最远的点
- 这两个距离中的最大值就是答案
实现方法：
- 进行三次 BFS：
- 从任意节点开始，找到最远的节点 A
- 从 A 开始，记录到所有节点的距离 distA
- 从 B（与 A 不同颜色）开始，记录到所有节点的距离 distB
- 答案 = max(从白色到黑色的最远距离, 从黑色到白色的最远距离)
- 进行三次 BFS：
代码实现
#include<bits/stdc++.h>usingnamespacestd;constintN=1e5+5;// 最大节点数+5的缓冲区intn;// 树的节点数intc[N];// 颜色数组，c[i]表示节点i的颜色：0-白色，1-黑色vector<int>g[N];// 邻接表，存储树的结构intd[2][N];// 距离数组，d[0][i]表示从A到i的距离，d[1][i]表示从B到i的距离// BFS函数：从起点s开始进行广度优先搜索，计算到所有节点的距离// 参数：s - 起点，dist - 存储距离的数组指针// 返回值：BFS过程中最后访问的节点（即距离起点最远的节点）intbfs(ints,int*dist){queue<int>q;// BFS队列// 初始化距离数组，将所有距离设为-1表示未访问fill(dist+1,dist+n+1,-1);// 起点距离为0，加入队列dist[s]=0;q.push(s);intlast=s;// 记录最后访问的节点// BFS主循环while(!q.empty()){intu=q.front();q.pop();// 取出队首节点last=u;// 更新最后访问的节点// 遍历u的所有邻居for(intv:g[u]){// 如果邻居v尚未访问过if(dist[v]==-1){dist[v]=dist[u]+1;// 更新距离q.push(v);// 加入队列}}}returnlast;// 返回最后访问的节点（即最远节点）}intmain(){// 输入输出优化ios::sync_with_stdio(false);cin.tie(0);// 读入节点数cin>>n;// 读入每个节点的颜色for(inti=1;i<=n;i++)cin>>c[i];// 读入树的边，构建邻接表for(inti=1;i<n;i++){intu,v;cin>>u>>v;g[u].push_back(v);g[v].push_back(u);}// 第一步：第一次BFS，从任意节点(节点1)出发，找到最远点AintA=bfs(1,d[0]);// 第二步：第二次BFS，从A出发，找到最远点B// 同时，d[0]数组现在存储的是从A到所有节点的距离intB=bfs(A,d[0]);// 第三步：第三次BFS，从B出发// d[1]数组将存储从B到所有节点的距离bfs(B,d[1]);// 现在我们有：// d[0][i] - 从A到节点i的距离// d[1][i] - 从B到节点i的距离intans=0;// 存储最终答案（最远异色节点对的距离）// 情况1：考虑以A为端点的最远异色节点对// 遍历所有节点，找到与A颜色不同的节点，更新最大距离for(inti=1;i<=n;i++){if(c[i]!=c[A]){// 如果节点i与A颜色不同ans=max(ans,d[0][i]);// 更新答案，取当前最大值}}// 情况2：考虑以B为端点的最远异色节点对// 遍历所有节点，找到与B颜色不同的节点，更新最大距离for(inti=1;i<=n;i++){if(c[i]!=c[B]){// 如果节点i与B颜色不同ans=max(ans,d[1][i]);// 更新答案，取当前最大值}}// 输出最终答案cout<<ans<<"\n";return0;}功能分析
算法思路
- 核心思想：利用树的直径和 BFS 性质
- 关键观察：最远异色点对一定包含从某个点出发能到达的最远异色点
- 正确性保证：对于任意节点，其最远点一定是直径端点之一
时间复杂度
- 三次 BFS：O(n)
- 两次遍历所有节点：O(n)
- 总复杂度：O(n)，满足 n ≤ 10⁵ 的要求
空间复杂度
- 邻接表：O(n)
- 距离数组：O(n)
- 总空间：O(n)
注意事项
- 使用
ios::sync_with_stdio(false)和cin.tie(0)加速输入 - BFS 使用队列实现，避免递归栈溢出
- 颜色数组下标从 1 开始，符合题目输入
- 保证至少有一对异色节点（题目保证）
测试用例验证
对于样例：
5 0 1 0 1 0 1 2 1 3 3 4 3 5树结构：
1 / \ 2 3 / \ 4 5颜色：1(0), 2(1), 3(0), 4(1), 5(0)
最远异色点对：节点 2(黑) 和 节点 5(白)
距离 = 2->1->3->5 = 3
算法输出：3
各种学习资料，助力大家一站式学习和提升！！！
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}1、csp信奥赛高频考点知识详解及案例实践：
CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转
CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转
信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html
2、csp信奥赛冲刺一等奖有效刷题题解：
CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转
CSP信奥赛C++一等奖通关刷题题单及题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转
3、GESP C++考级真题题解：
GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转
GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转
GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html
4、CSP信奥赛C++竞赛拿奖视频课：
https://edu.csdn.net/course/detail/40437 点击跳转
· 文末祝福 ·
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}
