题目传送门(BZOJ)
>原文链接<

题解 :

这个东西好像是叫最大独立集?

状态 :F[i]代表选ii子树拜访数量,G[i]表示不选i的最大拜访数量。

转移 :F[i] = 1+\sum G[to[i]] , G[i] = \sum\max(G[to[i]], F[to[i]])

最后答案是\max(F[1], G[1])

代码 :

#include <cstdio>#include <cstring>#include <algorithm>#include <iostream>#include <queue>using namespace std;const int N = 50001;int n;int head[N],to[N<<1],next[N<<1],cnt;int f[N],g[N];void add_edge(int a,int b) { to[++cnt]=b; next[cnt]=head[a]; head[a]=cnt; to[++cnt]=a; next[cnt]=head[b]; head[b]=cnt;}void dfs(int p,int fa) { for(int i=head[p];i;i=next[i]) { if(to[i]!=fa) { dfs(to[i],p); f[p]+=g[to[i]]; g[p]+=max(g[to[i]],f[to[i]]); } } f[p]++;}int main() { scanf("%d",&n); for(int i=1;i<n;i++) { int a,b; scanf("%d%d",&a,&b); add_edge(a,b); } dfs(1,1); printf("%d\n",max(f[1],g[1]));}