# Bzoj1864 [zjoi2006]三色二叉树

Posted by yjjr's blog on February 6, 2018 1 minutes to read

Description

Input

Output

Sample Input

1122002010

Sample Output

5 2

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)
using namespace std;
const int maxn=3e5+6;
LL f[maxn][3],l[maxn],r[maxn],ans1,ans2,cnt=1;
{
char ch=getchar();
if(ch=='0')return;
}
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()
{
}