200 1 1
1122002010 5 2
Solution:
容易看出是树形Dp，且属于那种比较简单的树形Dp
由于要处理两个小问题，我们设f[i][0/1/2]（0->白，1->红，2—>黄）来表示以i为根的子树最多有几个白色节点，g[i][0/1/2]则表示最小的情况
首先我们要处理读入的问题，这里我采用了递归的方式，因为这里的节点其实是按照先序的方式来读入的，所以不断递归儿子到底后返回编号记入
之后就是转移了，按照先序遍历的顺序来转移，也就是至下而上，转移方程其实抠抠脚就可以出来了：
f[i][0]=max{f[u][1]+f[v][2],f[u][2]+f[v][1]}+1 //u、v表示左右儿子的编号，最后+1是为i节点自己为白色所以要比填其他颜色多1
f[i][1]=max{f[u][0]+f[v][2],f[u][2]+f[v][0]}
f[i][2]=max{f[u][1]+f[v][0],f[u][0]+f[v][1]}
最后把f[1][0],f[1][1],f[1][2]三个拿起来最大就是答案
g的转移和结果同理，把max改min即可。
Code：
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int inf=500050; 4 struct Node{ 5 int fa; 6 int son[2]; 7 }Tree[inf]; 8 char Str[inf]; 9 int f[inf][3],g[inf][3],tot,Y; 10 void Dfs(int pos){ 11 for(int i=0;i<=1;i++){ 12 if(!Tree[pos].son[i]) break; 13 Dfs(Tree[pos].son[i]); 14 } 15 f[pos][0]=max(f[Tree[pos].son[0]][1]+f[Tree[pos].son[1]][2],f[Tree[pos].son[0]][2]+f[Tree[pos].son[1]][1])+1; 16 f[pos][1]=max(f[Tree[pos].son[0]][0]+f[Tree[pos].son[1]][2],f[Tree[pos].son[0]][2]+f[Tree[pos].son[1]][0]); 17 f[pos][2]=max(f[Tree[pos].son[0]][1]+f[Tree[pos].son[1]][0],f[Tree[pos].son[0]][0]+f[Tree[pos].son[1]][1]); 18 g[pos][0]=min(g[Tree[pos].son[0]][1]+g[Tree[pos].son[1]][2],g[Tree[pos].son[0]][2]+g[Tree[pos].son[1]][1])+1; 19 g[pos][1]=min(g[Tree[pos].son[0]][0]+g[Tree[pos].son[1]][2],g[Tree[pos].son[0]][2]+g[Tree[pos].son[1]][0]); 20 g[pos][2]=min(g[Tree[pos].son[0]][1]+g[Tree[pos].son[1]][0],g[Tree[pos].son[0]][0]+g[Tree[pos].son[1]][1]); 21 } 22 int In(int F){ 23 Tree[++tot].fa=F; 24 int a=Str[++Y]-‘0‘,Num=tot; 25 if(a>=1) 26 Tree[Num].son[0]=In(Num); 27 if(a>=2) 28 Tree[Num].son[1]=In(Num); 29 return Num; 30 } 31 using namespace std; 32 int main() 33 { 34 freopen("tree.in","r",stdin); 35 freopen("tree.out","w",stdout); 36 scanf("%s",Str+1); 37 In(0); 38 Dfs(1); 39 printf("%d %d",max(f[1][2],max(f[1][0],f[1][1])),min(g[1][2],min(g[1][0],g[1][1]))); 40 return 0; 41 }
原文：https://www.cnblogs.com/Takarada-Rikka/p/11824775.html