欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！
专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。
适合人群：
- 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
- 希望系统学习C++/Python编程的初学者
- 想要提升算法与编程能力的编程爱好者
附上汇总帖：GESP认证C++编程真题解析 | 汇总
【题目来源】
洛谷：[P10725 GESP202406 八级] 最远点对 - 洛谷
【题目描述】
小杨有一棵包含n nn个节点的树，这棵树上的任意一个节点要么是白色，要么是黑色。
小杨想知道相距最远的一对不同颜色节点的距离是多少。
【输入】
第一行包含一个正整数n nn，代表树的节点数。
第二行包含n nn个非负整数a 1 , a 2 , … , a n a_1,a_2,\dots,a_na1,a2,…,an（对于所有的1 ≤ i ≤ n 1\le i\le n1≤i≤n，均有a i a_iai等于 0 或 1），其中如果a i = 0 a_i=0ai=0，则节点i ii的颜色为白色；如果a i = 1 a_i=1ai=1，则节点i ii的颜色为黑色。
之后n − 1 n-1n−1行，每行包含两个正整数x i , y i x_i,y_ixi,yi，代表存在一条连接节点x i x_ixi和y i y_iyi的边。
保证输入的树中存在不同颜色的点。
【输出】
输出一个整数，代表相距最远的一对不同颜色节点的距离。
【输入样例】
5 0 1 0 1 0 1 2 1 3 3 4 3 5【输出样例】
3【算法标签】
《洛谷 P10725 最远点对》 #树的遍历# #GESP# #2024#
【代码详解】
#include<bits/stdc++.h>usingnamespacestd;constintN=100005,M=N*2;intn;// 节点数inta[N];// a[i]: 节点i的颜色，0或1intcol0[N],col1[N];// col0[i]: 以节点i为根的子树中，距离i最近的0色节点的距离// col1[i]: 以节点i为根的子树中，距离i最近的1色节点的距离intans;// 答案：最长异色路径长度inth[N],e[M],ne[M],w[M],idx;// 邻接表存储树// 添加无向边voidadd(inta,intb,intc){e[idx]=b;// 边的终点w[idx]=c;// 边权，这里都是1ne[idx]=h[a];// 插入到链表头部h[a]=idx;// 更新头指针idx++;// 边编号自增}// 深度优先搜索// u: 当前节点// fa: 父节点voiddfs(intu,intfa){// 初始化当前节点的col0和col1if(a[u]==1){col1[u]=0;// 如果当前节点是1色，距离为0}else{col0[u]=0;// 如果当前节点是0色，距离为0}// 遍历所有邻居节点for(inti=h[u];i!=-1;i=ne[i]){intj=e[i];// 邻居节点if(j==fa)// 如果是父节点，跳过{continue;}// 递归处理子树dfs(j,u);// 关键：更新答案// 如果u是0色，j的子树中有1色节点，形成异色路径if(col0[u]>=0&&col1[j]>=0){ans=max(ans,col1[j]+col0[u]+1);}// 如果u是1色，j的子树中有0色节点，形成异色路径if(col1[u]>=0&&col0[j]>=0){ans=max(ans,col0[j]+col1[u]+1);}// 更新当前节点的col0和col1col1[u]=max(col1[u],col1[j]+1);col0[u]=max(col0[u],col0[j]+1);}}intmain(){// 输入节点数cin>>n;// 初始化邻接表memset(h,-1,sizeof(h));// 输入每个节点的颜色for(inti=1;i<=n;i++){cin>>a[i];// 初始化col0和col1为负无穷col0[i]=-1e9;col1[i]=-1e9;}// 输入n-1条边，构建树for(inti=1;i<n;i++){intu,v;cin>>u>>v;add(u,v,1);// 添加无向边，边权为1add(v,u,1);}// 从节点1开始DFSdfs(1,0);// 输出答案cout<<ans<<endl;return0;}【运行结果】
5 0 1 0 1 0 1 2 1 3 3 4 3 5 3
)
