A29787. 树上移动
填空题
困难
知识点
题目描述
树上移动
时间限制：1.0 s 内存限制：512.0 MB
题目描述
小杨有一棵包含n个节点的树，其中节点的编号从1到n，每个节点的颜色要么是白色要么是黑色。小杨可以任意选择节点s和节点t并从节点s出发移动到节点t，移动过程中小杨不能够经过重复节点。
小杨希望自己在至多经过k个黑色节点的前提下，经过的总节点数尽可能多，请你帮小杨选择经过最多的节点数是多少。
输入格式
第一行包含两个正整数 n,k，代表节点数量和至多经过的黑色节点数。
第二行包含n个正整数 a1,a2,,,,an，代表节点颜色，如果 ai=0 ，代表节点颜色为白色，如果 ai=1，代表节点颜色为黑色。
之后 n- 1 行，每行包含两个正整数 ui,vi，代表存在一条连接节点 ui 和 vi 的边。
输出格式
输出一个正整数，代表最多经过的节点数。
输入样例
5 1
0 0 1 1 1
1 2
2 3
2 5
1 4
输出样例
3
参考答案
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1010;
vector<int> g[N];
int a[N];
int n,k;
int ans;
void dfs(int x,int fa,int tot,int le) {
tot+=a[x];
if(tot>k) {
ans = max(ans,le);
return;
}
le++;
ans = max(ans,le);
for (int i:g[x]) {
if(i!=fa) {
dfs(i,x,tot,le);
}
}
}
int main() {
cin>>n>>k;
for (int i=1;i<=n;i++) {
cin>>a[i];
}
for (int i=1;i<n;i++) {
int u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
for (int i=1;i<=n;i++) {
dfs(i,0,0,0);
}
cout<<ans<<"\n";
}
上一题
下一题