2024年9月GESP真题及题解(C++八级): 美丽路径

2024年9月GESP真题及题解(C++八级): 美丽路径

题目描述

小杨有一棵包含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​的边。

输出格式

输出一个整数，代表最长美丽路径的长度。

输入输出样例 1

输入 1

5 1 0 0 1 0 1 2 3 5 4 3 1 3

输出 1

4

输入输出样例 2

输入 2

5 0 0 0 0 0 1 2 2 3 3 4 4 5

输出 2

1

说明/提示

对于全部数据，保证有1 ≤ n ≤ 10 5 , 0 ≤ c i ≤ 1 1 \leq n \leq 10^5,0 \leq c_i \leq 11≤n≤105,0≤ci​≤1，同时保证给出的数据构成一棵树。

思路分析

我们需要在树上找到最长的路径，使得路径上相邻节点颜色不同（即颜色交替）。

关键点：

1. 这是一棵树（无环、无向连通图）
2. 路径必须是简单的（不重复节点）
3. 要求相邻节点颜色不同

问题转化：

这本质上是求树的"直径"，但增加了颜色交替的限制。我们可以用两次DFS/BFS或树形DP来解决。

思路：

对于无颜色限制的树直径，经典做法是：

1. 任选一点开始DFS/BFS，找到最远的点A
2. 从点A开始DFS/BFS，找到最远的点B
3. A到B的距离就是直径

对于有颜色限制的情况，我们需要在DFS/BFS时跟踪颜色信息：

• 从节点u走到节点v的条件是：color[u] ≠ color[v]
• 需要记录从起点到每个节点的距离，但距离计算基于颜色交替

算法设计：

方法一：两次DFS/BFS（类似求树直径）

1. 从任意节点开始，进行DFS/BFS，但只能走颜色交替的边，找到最远的节点A
2. 从节点A开始，同样只走颜色交替的边，找到最远的节点B
3. A到B的节点数就是最长美丽路径长度

方法二：树形DP
对于每个节点u，考虑两种情况：

1. 以u为中间节点的路径：从u向下延伸，选两个不同的子树，得到两条颜色交替的路径，拼接起来
2. 以u为端点的路径：从u向下延伸的最长路径

定义状态：

• f[u][0]: 从u出发向子树走，且第一个孩子与u颜色相同的最长路径（实际上这种情况不存在于美丽路径）
• f[u][1]: 从u出发向子树走，且第一个孩子与u颜色不同的最长路径

但实际上我们只需要记录从u出发的最长和次长美丽路径，然后考虑拼接。

具体实现：

用DFS进行树形DP：

1. 对于每个节点u，遍历其所有子节点v
2. 如果color[u] ≠ color[v]，则可以从u走到v
3. 维护从u出发的最长美丽路径长度len1和次长len2
4. 对于节点u，可能的美丽路径有两种：
   • 从u向下的最长路径：len1 + 1
   • 通过u连接两条向下路径：len1 + len2 + 1
5. 全局维护最大值

复杂度：

• 时间复杂度：O(n)，每个节点访问一次
• 空间复杂度：O(n)

代码实现

#include<bits/stdc++.h>usingnamespacestd;constintN=1e5+5;intn;intc[N];// 节点颜色vector<int>g[N];// 邻接表intans=1;// 至少为1（单个节点）// DFS返回从u出发的最长美丽路径长度intdfs(intu,intfa){intlen1=0,len2=0;// 最长和次长for(intv:g[u]){if(v==fa)continue;intchild_len=dfs(v,u);// 如果颜色不同，才能走这条边if(c[u]!=c[v]){// 更新最长和次长if(child_len>len1){len2=len1;len1=child_len;}elseif(child_len>len2){len2=child_len;}}}// 情况1：以u为中间节点的路径ans=max(ans,len1+len2+1);// 情况2：以u为端点的路径ans=max(ans,len1+1);// 返回从u出发的最长路径长度returnlen1+1;}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);}dfs(1,0);cout<<ans<<endl;return0;}

功能分析

代码结构：

1. 输入处理：读取节点数、颜色、边
2. 建图：使用邻接表存储树
3. DFS递归：计算每个节点向下的最长美丽路径
4. 答案更新：维护全局最长美丽路径长度

核心逻辑：

• dfs(u, fa)返回从节点u出发向子树方向的最长美丽路径节点数
• 遍历所有子节点，只考虑颜色不同的边
• 对于每个节点，记录从其出发的最长和次长美丽路径
• 用len1 + len2 + 1更新答案（通过u连接两条路径）
• 用len1 + 1更新答案（以u为端点的路径）

复杂度分析：

• 时间复杂度：O(n)，每个节点访问一次
• 空间复杂度：O(n)，存储树和递归栈

测试样例验证

样例1：

输入： 5 1 0 0 1 0 1 2 3 5 4 3 1 3 输出： 4

路径：2-1-3-4 是美丽路径，长度为4。

样例2：

输入： 5 0 0 0 0 0 1 2 2 3 3 4 4 5 输出： 1

所有节点颜色相同，没有相邻节点颜色不同的路径，只能选单个节点。

各种学习资料，助力大家一站式学习和提升！！！

#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;}