Description
Input
仅有一行，不超过500000个字符，表示一个二叉树序列。
Output
输出文件也只有一行，包含两个数，依次表示最多和最少有多少个点能够被染成绿色。
Sample Input
1122002010
Sample Output
5 2
HINT
Source
Day1
树形DP~
先把字符串转成树，再在树上DP即可~
用f[i][0]表示i点不是绿色的最大/最小结果，f[i][1]表示i点是绿色的最大/最小结果。
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;int n,fi[500001],w[1000001],ne[1000001],cnt,tot,f[500001][2],now;
char s[500001];void add(int u,int v)
{w[++cnt]=v;ne[cnt]=fi[u];fi[u]=cnt;w[++cnt]=u;ne[cnt]=fi[v];fi[v]=cnt;}void dfs(int u)
{if(u==n+1) return;now++;if(s[u]=='0') return;if(s[u]=='1') add(u,u+1),dfs(u+1);else{add(u,u+1);dfs(u+1);add(u,now+1);dfs(now+1);}
}void cal1(int u,int fa)
{f[u][1]=1;int now=0,maxx=0,tot=0,a[3];for(int i=fi[u];i;i=ne[i])if(w[i]!=fa){cal1(w[i],u);a[tot++]=w[i];f[u][1]+=f[w[i]][0];}if(tot==1) f[u][0]=max(f[a[0]][0],f[a[0]][1]);else if(tot==2) f[u][0]=max(f[a[0]][0]+f[a[1]][1],f[a[0]][1]+f[a[1]][0]);
}void cal2(int u,int fa)
{int now=0,maxx=0,tot=0,a[3];for(int i=fi[u];i;i=ne[i])if(w[i]!=fa){cal2(w[i],u);a[tot++]=w[i];}if(!tot){f[u][1]=1;f[u][0]=0;return;}if(tot==1) f[u][0]=min(f[a[0]][0],f[a[0]][1]),f[u][1]=f[a[0]][0]+1;else if(tot==2){f[u][0]=min(f[a[0]][0]+f[a[1]][1],f[a[0]][1]+f[a[1]][0]);f[u][1]=f[a[0]][0]+f[a[1]][0]+1;}
}int main()
{scanf("%s",s+1);n=strlen(s+1);dfs(1);cal1(1,1);printf("%d ",max(f[1][0],f[1][1]));memset(f,127/3,sizeof(f));cal2(1,1);printf("%d\n",min(f[1][0],f[1][1]));return 0;
}