: 树上移动)
2024年12月GESP真题及题解(C++八级): 树上移动
题目描述
小杨有一棵包含n nn个节点的树，其中节点的编号从1 11到n nn，每个节点的颜色要么是白色要么是黑色，小杨可以任意选择节点s ss和节点t tt并从节点s ss出发移动到节点t tt，移动过程中小杨不能够经过重复节点。
小杨希望自己在至多经过k kk个黑色节点的前提下，经过的总节点数尽可能多，请你帮小杨选择经过最多的节点数是多少。
输入格式
第一行包含两个正整数n , k n,kn,k，代表节点数量和至多经过的黑色节点数。
第二行包含n nn个正整数a 1 , a 2 , … , a n a_1,a_2,\dots,a_na1,a2,…,an，代表节点颜色，如果a i = 0 a_i=0ai=0，代表节点颜色为白色，如果a i = 1 a_i=1ai=1，代表节点颜色为黑色。
之后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 1 1 1 2 2 3 2 5 1 4输出 1
3说明/提示
| 子任务编号 | 数据点占比 | n nn | k kk | 特殊性质 |
|---|---|---|---|---|
| 1 11 | 20 % 20\%20% | ≤ 100 \leq 100≤100 | ≤ 100 \leq 100≤100 | 树的形态为一条链 |
| 2 22 | 20 % 20\%20% | ≤ 1000 \leq 1000≤1000 | 0 00 | |
| 3 33 | 60 % 60\%60% | ≤ 1000 \leq 1000≤1000 | ≤ 1000 \leq 1000≤1000 |
对于全部数据，保证有1 ≤ n ≤ 1000 1\leq n\leq 10001≤n≤1000，0 ≤ k ≤ 1000 0\leq k\leq 10000≤k≤1000，0 ≤ a i ≤ 1 0\leq a_i\leq 10≤ai≤1。
思路分析
问题理解：
在给定的树上寻找一条简单路径（无重复节点），使得路径上黑色节点的数量不超过k，并且路径的节点数尽可能多。核心思路：
- 树中任意简单路径由两个端点唯一确定。
- 枚举每个节点作为路径起点，通过 BFS 计算从该起点到所有其他节点的距离和黑色节点数。
- 对于每一对起点和终点，检查黑色节点数是否不超过
k，并更新最大节点数。
算法步骤：
- 读取输入，构建树的邻接表。
- 初始化答案
ans = 0。 - 对每个节点
i（作为起点）执行 BFS：- 初始化距离数组
d和黑色节点计数数组b。 - 起点
i的距离为 0，黑色节点数为c[i]。 - 使用队列进行 BFS，对于每个访问的节点
u，检查从i到u的路径是否满足条件，并更新ans。 - 对于
u的每个未访问邻居v，更新距离和黑色节点数，并入队。
- 初始化距离数组
- 输出
ans。
代码实现
#include<bits/stdc++.h>usingnamespacestd;intmain(){intn,k;cin>>n>>k;// 读取节点数和允许的最大黑色节点数vector<int>c(n+1);// 节点颜色，c[i] = 0 白色，1 黑色for(inti=1;i<=n;++i){cin>>c[i];}vector<vector<int>>g(n+1);// 邻接表存储树for(inti=0;i<n-1;++i){intu,v;cin>>u>>v;g[u].push_back(v);g[v].push_back(u);}intans=0;// 记录答案（最多经过的节点数）// 枚举每个节点作为路径起点for(inti=1;i<=n;++i){vector<int>d(n+1,-1);// d[j] 表示从 i 到 j 的边数（距离）vector<int>b(n+1,0);// b[j] 表示从 i 到 j 路径上的黑色节点数queue<int>q;// 起点初始化d[i]=0;b[i]=c[i];// 路径包含起点，计入其颜色q.push(i);while(!q.empty()){intu=q.front();q.pop();// 当前路径从 i 到 u 的黑色节点数满足条件，更新答案// 经过的节点数 = 距离 + 1if(b[u]<=k){ans=max(ans,d[u]+1);}// 遍历邻居节点for(intv:g[u]){if(d[v]==-1){// 未访问过d[v]=d[u]+1;// 距离增加一条边b[v]=b[u]+(c[v]==1?1:0);// 累加黑色节点数q.push(v);}}}}cout<<ans<<endl;// 输出结果return0;}功能分析
复杂度：
- 时间复杂度：O(n²)。每个起点执行一次 BFS，每次 BFS 访问所有节点，共 n 个起点。
- 空间复杂度：O(n²)。邻接表存储 O(n) 条边，BFS 中使用 O(n) 的临时数组。
注意事项：
- 路径可以是单个节点（起点等于终点）。
- 如果没有任何路径满足黑色节点数不超过
k，则输出 0。 - 使用
-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;}
