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

题解 :

这是一道非常基础的树形DP。

读入部分递归的去初始化每个节点。

状态 : F[i][0/1]代表i节点选或不选绿色的最大/最小方案数(分别求一遍)

转移 : F[i][1] =F[ls][0]+F[rs][0]+1 F[i][0] = \max(F[ls][0]+F[rs][1], F[rs][0]+F[ls][1])

求最小值把\max换成\min即可

答案是\max(F[1][0], F[1][1])

代码 :

#include <cstdio>#include <cstring>#include <iostream>#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 100000, stdin), p1==p2)?EOF:*p1++)#define rev(i, p) for(Edge *i = h[p]; i; i = i->next)#define rep(i, a, b) for(int i = a; i <= b; i ++ )char buf[100000],*p1,*p2;const int N = 510000;int n = 1, ch[N][2];#define ls ch[p][0]#define rs ch[p][1]int f[N][2], ans1, ans2;void init(int p) { int siz = nc()^48; for(int i = 0; i < siz; i ++ ) ch[p][i] = ++n, init(n);}void dfs1(int p) { if(!p) return ; dfs1(ls), dfs1(rs); f[p][1] = f[ls][0]+f[rs][0]+1; f[p][0] = std :: max(f[ls][0]+f[rs][1], f[rs][0]+f[ls][1]);}void dfs2(int p) { if(!p) return ; dfs2(ls), dfs2(rs); f[p][1] = f[ls][0]+f[rs][0]+1; f[p][0] = std :: min(f[ls][0]+f[rs][1], f[rs][0]+f[ls][1]);}int main() { init(1); dfs1(1); ans1 = std :: max(f[1][0], f[1][1]); memset(f, 0, sizeof f); dfs2(1); ans2 = std :: min(f[1][0], f[1][1]); printf("%d %d\n", ans1, ans2);}