欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！
专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。
适合人群：
- 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
- 希望系统学习C++/Python编程的初学者
- 想要提升算法与编程能力的编程爱好者
附上汇总帖：GESP认证C++编程真题解析 | 汇总
【题目来源】
洛谷：P11251 [GESP202409 八级] 美丽路径 - 洛谷
【题目描述】
小杨有一棵包含n nn个节点的树，节点从1 11到n nn编号，并且每个节点要么是白色，要么是黑色。
对于树上的一条简单路径（不经过重复节点的路径），小杨认为它是美丽的当且仅当路径上相邻节点的颜色均不相同。例如下图，其中节点1 11和节点4 44是黑色，其余节点是白色，路径2 − 1 − 3 − 4 2-1-3-42−1−3−4是美丽路径，而路径2 − 1 − 3 − 5 2-1-3-52−1−3−5不是美丽路径（相邻节点3 33和5 55颜色相同）。
对于树上的一条简单路径，小杨认为它的长度是路径包含节点的数量。小杨想知道最长的美丽路径的长度是多少。
【输入】
第一行包含一个正整数n nn，代表节点数量。
第二行包含n nn个整数c 1 , c 2 , … , c n c_1,c_2,\dots,c_nc1,c2,…,cn，代表每个节点的颜色，如果c i = 0 c_i=0ci=0，代表节点i ii为白色，如果c i = 1 c_i=1ci=1，代表节点i ii为黑色。
之后n − 1 n-1n−1行，每行包含两个正整数u i , v i u_i,v_iui,vi，代表存在一条连接节点u i u_iui和节点v i v_ivi的边。
【输出】
输出一个整数，代表最长美丽路径的长度。
【输入样例】
5 1 0 0 1 0 1 2 3 5 4 3 1 3【输出样例】
4【算法标签】
《洛谷 P11251 美丽路径》 #动态规划DP# #GESP# #2024#
【代码详解】
#include<bits/stdc++.h>usingnamespacestd;constintN=100005,M=N*2;intn;// 节点数量intc[N];// c[i] 表示节点i的颜色intf1[N];// f1[i]: 以节点i为起点的最长同色路径长度intf2[N];// f2[i]: 以节点i为起点的次长同色路径长度intans;// 最终答案（路径上的节点数-1，即最大长度）inth[N],e[M],ne[M],idx;// 邻接表存储树// 添加无向边voidadd(inta,intb){e[idx]=b;ne[idx]=h[a];h[a]=idx++;}// 深度优先搜索// u: 当前节点// fa: 父节点voiddfs(intu,intfa){// 遍历所有邻接节点for(inti=h[u];i!=-1;i=ne[i]){intj=e[i];// 邻接节点if(j==fa)// 跳过父节点{continue;}// 递归处理子树dfs(j,u);// 计算从当前节点u到子节点j的路径长度// 如果u和j颜色不同，路径长度为f1[j]+1，否则为0intt=(c[u]!=c[j]?f1[j]+1:0);// 更新f1[u]和f2[u]if(t>f1[u]){f2[u]=f1[u];// 原来的最大值变为次大值f1[u]=t;// 更新最大值}elseif(t>f2[u]){f2[u]=t;// 更新次大值}}// 更新答案：考虑经过节点u的最长同色路径// 注意：这里计算的是路径上的边数，而不是节点数ans=max(ans,f1[u]+f2[u]);}intmain(){cin>>n;// 初始化邻接表memset(h,-1,sizeof(h));idx=0;// 读取每个节点的颜色for(inti=1;i<=n;i++){cin>>c[i];}// 读取树的边for(inti=1;i<n;i++){intu,v;cin>>u>>v;add(u,v);add(v,u);}// 从节点1开始DFSdfs(1,0);// 输出结果：最长同色路径的节点数 = 边数 + 1cout<<ans+1<<endl;return0;}【运行结果】
5 1 0 0 1 0 1 2 3 5 4 3 1 3 4
