[ZJOI2006]三色二叉树
2024-09-05 19:13:05
[ZJOI2006]三色二叉树
#include<bits/stdc++.h>
using namespace std;
const int _=500005;
int n,now;
int ls[_],rs[_],r[_],g[_],b[_];
char s[_];
void bu(int u){
if(s[u]=='1'||s[u]=='2'){++now;bu(ls[u]=now);}
if(s[u]=='2'){++now;bu(rs[u]=now);}
}
void qmax(int u){
if(s[u]=='0'){g[u]=1;r[u]=0;b[u]=0;return;}
if(s[u]=='1'){
int v=ls[u];qmax(v);
g[u]=max(b[v],r[v])+1;
r[u]=max(g[v],b[v]);
b[u]=max(g[v],r[v]);
}
if(s[u]=='2'){
qmax(ls[u]);qmax(rs[u]);
g[u]=max(b[ls[u]]+r[rs[u]],r[ls[u]]+b[rs[u]])+1;
b[u]=max(g[ls[u]]+r[rs[u]],r[ls[u]]+g[rs[u]]);
r[u]=max(b[ls[u]]+g[rs[u]],g[ls[u]]+b[rs[u]]);
}
}
void qmin(int u){
if(s[u]=='0'){g[u]=1;r[u]=0;b[u]=0;return;}
if(s[u]=='1'){
int v=ls[u];qmin(v);
g[u]=min(b[v],r[v])+1;
r[u]=min(g[v],b[v]);
b[u]=min(g[v],r[v]);
}
if(s[u]=='2'){
qmin(ls[u]);qmin(rs[u]);
g[u]=min(b[ls[u]]+r[rs[u]],r[ls[u]]+b[rs[u]])+1;
b[u]=min(g[ls[u]]+r[rs[u]],r[ls[u]]+g[rs[u]]);
r[u]=min(b[ls[u]]+g[rs[u]],g[ls[u]]+b[rs[u]]);
}
}
int main(){
scanf("%s",s+1);n=strlen(s+1);
bu(now=1);
qmax(1);
printf("%d ",max(g[1],max(r[1],b[1])));
memset(g,63,sizeof(g));
memset(r,63,sizeof(r));
memset(b,63,sizeof(b));
qmin(1);
printf("%d\n",min(g[1],min(b[1],r[1])));
return 0;
}
最新文章
- cmd 下telnet 不是内部或外部命令
- assets中放入中文文件名导致Android Studio编译错误
- oracle/sqlserver 递归
- 三种对话框的示例(alert,confirm,prompt)
- Swift中KIF测试的特点-b
- 图论 BZOJ 3669 [Noi2014]魔法森林
- 实现C++模板类头文件和实现文件分离的方法
- [Angular Tutorial] 2-Angular Templates
- (MonoGame从入门到放弃-2) 初识MonoGame
- Linux基本操作——文件相关
- js中的单例模式
- linux 一键安装lnmp环境
- C# 获得本机IP、端口等信息地址以及服务器IP信息
- svn使用openldap验证apache访问方式
- ctype
- ASP.NET CORE下用盛派微信SDK取微信openid
- ionic框架
- android R.layout 中找不到已存在的布局文件
- css 页面定位position
- 不使用ref