标签：树形DP
Description
Input
仅有一行，不超过500000个字符，表示一个二叉树序列。
Output
输出文件也只有一行，包含两个数，依次表示最多和最少有多少个点能够被染成绿色。
Sample Input
1122002010
Sample Output
5 2
题意：给定一棵二叉树，将其染色（红，绿，蓝），其父亲节点必须和两个儿子节点染上不同的颜色，两个儿子节点也必须染不同颜色，问最多最少有多少个节点被染成绿色
分析：f[i][0]表示当前节点没染绿色的最大值 f[i][1]表示当前节点染上绿色的最大值
F[i][0]=max(f[l[x]][1]+f[r[x]][0] ,f[l[x]][0]+f[r[x]][1]);
F[i][1]=f[l[x]][0]+f[r[x]][0]+1
最小值同理
Code
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define LL long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=head[x];i;i=e[i].next)
using namespace std;
const int maxn=3e5+6;
LL f[maxn][3],l[maxn],r[maxn],ans1,ans2,cnt=1;
inline void read(int x)
{
char ch=getchar();
if(ch=='0')return;
cnt++;l[x]=cnt;read(cnt);
if(ch=='2'){cnt++;r[x]=cnt;read(cnt);}
}
void dp1(int x)
{
if(!x)return ;
dp1(l[x]);dp1(r[x]);
f[x][1]=f[l[x]][0]+f[r[x]][0]+1;
f[x][0]=max(f[l[x]][0]+f[r[x]][1],f[r[x]][0]+f[l[x]][1]);
}
void dp2(int x)
{
if(!x)return;
dp2(l[x]);dp2(r[x]);
f[x][1]=f[l[x]][0]+f[r[x]][0]+1;
f[x][0]=min(f[l[x]][0]+f[r[x]][1],f[r[x]][0]+f[l[x]][1]);
}
int main()
{
read(1);
mem(f,0);
dp1(1);ans1=max(f[1][1],f[1][0]);
mem(f,0);
dp2(1);ans2=min(f[1][1],f[1][0]);
printf("%lld %lld\n",ans1,ans2);
return 0;
}
