Bzoj1864 [zjoi2006]三色二叉树

Posted by yjjr's blog on February 6, 2018

标签:树形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;
}


本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr