题目在这里
————————————————————————————————
三色二叉树
首先 题面写的很清楚了 是一道树状数组题
因为这题的输入方式很特别 按二叉树序列 所以在输入上要特殊处理
如下
void read(int x)
{//读入+存图 以左右子树为形式 如l[x]=y即y为x左子树
char ch=getchar();
if(ch=='0')return;
l[x]=++cnt;
read(cnt);
if(ch=='2')
{
r[x]=++cnt;
read(cnt);
}
}
以字符形式读入 同时建好了左右子树图 比起整体读入再处理的方法便捷很多
然后 是简单的利用dfs遍历最大值和最小值的操作
状态转移方程如下：
zl[x][1]=zl[l[x]][0]+zl[r[x]][0]+1;
zl[x][0]=max(zl[l[x]][0]+zl[r[x]][1],zl[l[x]][1]+zl[r[x]][0]);
有注释 不再多言
void DrRatio(int x)//最大值 dfs
{
if(!x)return;
DrRatio(l[x]);
DrRatio(r[x]);
zl[x][1]=zl[l[x]][0]+zl[r[x]][0]+1;
zl[x][0]=max(zl[l[x]][0]+zl[r[x]][1],zl[l[x]][1]+zl[r[x]][0]);
//三者颜色必定不同 故若x不染色 l[x] r[x]必定有其一染色
//同理若x染色 则l[x] r[x] 必定不染色
}
void Silwolf(int x)//最小值
{
if(!x)return;
Silwolf(l[x]);
Silwolf(r[x]);
zl[x][1]=zl[l[x]][0]+zl[r[x]][0]+1;
zl[x][0]=min(zl[l[x]][0]+zl[r[x]][1],zl[l[x]][1]+zl[r[x]][0]);
}
最后就是很简单的输出
总结一下 这道题难点就在于清晰地认识到填色方法 以及将输入数据处理成图的操作
（还有 记得置零
code:
点击查看代码
#include <bits/stdc++.h>
#define fo(x,y,z) for(int (x)=(y);(x)<=(z);(x)++)
#define fu(x,y,z) for(int (x)=(y);(x)>=(z);(x)--)
#define foo(x,y,z) for(int (x)=(y);(x)<(z);(x)++)
using namespace std;
inline int qr()
{
char ch=getchar();int x=0,f=1;
for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);
return x*f;
}
#define qr qr()
typedef long long ll;
const int Ratio=0;
const int N=100005;
const int maxx=0x7f7f7f7f;
ll zl1,zl2,cnt=1;
ll zl[N][5],l[N],r[N];//zl[i][0] 第i块不染色 。。[1]染色
void read(int x)
{//读入+存图 以左右子树为形式 如l[x]=y即y为x左子树
char ch=getchar();
if(ch=='0')return;
l[x]=++cnt;
read(cnt);
if(ch=='2')
{
r[x]=++cnt;
read(cnt);
}
}
void DrRatio(int x)//最大值 dfs
{
if(!x)return;
DrRatio(l[x]);
DrRatio(r[x]);
zl[x][1]=zl[l[x]][0]+zl[r[x]][0]+1;
zl[x][0]=max(zl[l[x]][0]+zl[r[x]][1],zl[l[x]][1]+zl[r[x]][0]);
//三者颜色必定不同 故若x不染色 l[x] r[x]必定有其一染色
//同理若x染色 则l[x] r[x] 必定不染色
}
void Silwolf(int x)//最小值
{
if(!x)return;
Silwolf(l[x]);
Silwolf(r[x]);
zl[x][1]=zl[l[x]][0]+zl[r[x]][0]+1;
zl[x][0]=min(zl[l[x]][0]+zl[r[x]][1],zl[l[x]][1]+zl[r[x]][0]);
}
void op()
{
printf("%lld %lld\n",zl1,zl2);
}
int main()
{
read(cnt);
memset(zl,0,sizeof zl);
DrRatio(1);
zl1=max(zl[1][1],zl[1][0]);
memset(zl,0,sizeof zl);
Silwolf(1);
zl2=min(zl[1][1],zl[1][0]);
op();
return Ratio;
}