BZOJ1864 - Click Here
Description
Input
仅有一行，不超过500000个字符，表示一个二叉树序列。
Output
输出文件也只有一行，包含两个数，依次表示最多和最少有多少个点能够被染成绿色。
Solutions
首先这个序列很容易证明一个序列对应一棵树，也就是说一个序列不会存在多种形态的树(左右节点交换的不算)。因此，只用DFS一下，很容易得到这棵树。
然后就是很暴力的树形DP了。
设$f[i][1/0]$表示第$i$个节点，是或不是绿色时的最优解。
根据题目的要求，易得转移方程(以下为最大解的转移方程，最小解类似)
$\begin{cases} f[i][1]=1,son(i)=0 \\ f[i][1]=f[j][0]+1,son(i)=1 \\ f[i][1]=f[L][0]+f[R][0]+1,son(i)=2 \end{cases}$
$\begin{cases} f[i][0]=0,son(i)=0 \\ f[i][0]=max(f[j][0],f[j][1]),son(i)=1 \\ f[i][0]=max(f[L][0]+f[R][1],f[L][1]+f[R][0]),son(i)=2 \end{cases}$
$son(i)$表示$i$节点的儿子个数。
CODE
CODE - Click Here