每日一题 6月2日 旅游 树的最大独立集
题目链接：https://ac.nowcoder.com/discuss/434394
#include <bits/stdc++.h>
#define LL long long
using namespace std;
vector<int> v[500005];
int f[500005][2];
void DFS(int u, int fa){
f[u][1]=1;
for(auto x: v[u]){
if(x!=fa){
DFS(x, u);
f[u][1]+=f[x][0];
f[u][0]+=max(f[x][0], f[x][1]);
}
}
}
int main(){
int n, s, x, y; scanf("%d%d", &n, &s);
for(int i=1; i<n; i++){
scanf("%d%d", &x, &y);
v[x].push_back(y);
v[y].push_back(x);
}
DFS(s, 0);
printf("%d\n", f[s][1]);
return 0;
}
查看28道真题和解析
