简答题
偏难
#20618
树上移动 时间限制:1.0 s 内存限制:512.0 MB 题面描述 小杨有一棵包含 n 个节点的树,其中节点的编号从 1 到 n ,每个节点的颜色要么是白色要…
树上移动
时间限制: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的边。
输出格式
输出一个正整数,代表最多经过的节点数。
输入样例
输入样例

对于全部数据,保证有 1≤n≤1000,0≤k≤1000,0≤ai≤1。
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#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";
}</pre>
这道题暂未补解析。