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

题解 :

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

状态 :$F[i]$代表选$i$的$i$子树拜访数量,$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]));}