和没有上司的舞会类似,但是需要注意的是这是一个二叉树,首先对于只有一个节点和没有节点的时候,和上司的舞会完全相同,但是如果要是有两个儿子的时候我们需要注意,三个点必须有且只有一个是绿色也就是1,剩下的完全相同。
代码如下
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std ;
const int N = 5e5 + 10 ;
const int M = 2 * N ;
int g[N] ;
char s[N] ;
int l[N] , r[N] ;
int cnt ;
void dfs(int u){
++ cnt ;
if(g[u] == 0) return ;
else if(g[u] == 1) {
l[u] = cnt + 1 ;
dfs(cnt + 1) ;
}
else {
l[u] = cnt + 1 ;
dfs(cnt + 1) ;
r[u] = cnt + 1 ;
dfs(cnt + 1) ;
}
}
int f[N][2] , _f[N][2] ;
void _dfs(int u){
if(g[u] == 0){
f[u][1] = 1 ;
_f[u][1] = 1 ;
}
else if(g[u] == 1){
_dfs(l[u]) ;
f[u][1] = 1 + f[l[u]][0] ;
f[u][0] = max(f[l[u]][0] , f[l[u]][1]) ;
_f[u][1] = 1 + _f[l[u]][0] ;
_f[u][0] = min(_f[l[u]][0] , _f[l[u]][1]) ;
}else {
_dfs(l[u]) ;
_dfs(r[u]) ;
f[u][0] = max(f[l[u]][0] + f[r[u]][1] , f[l[u]][1] + f[r[u]][0]) ;
f[u][1] = f[l[u]][0] + f[r[u]][0] + 1 ;
_f[u][0] = min(_f[l[u]][0] + _f[r[u]][1] , _f[l[u]][1] + _f[r[u]][0]) ;
_f[u][1] = _f[l[u]][0] + _f[r[u]][0] + 1 ;
}
}
int main(void){
scanf("%s" , s + 1) ;
int n = strlen(s + 1) ;
for(int i = 1 ; i <= n ; i ++){
g[i] = s[i] - '0' ;
}
dfs(1) ;
_dfs(1) ;
printf("%d %d" , max(f[1][0] , f[1][1]) , min(_f[1][0] , _f[1][1])) ;
}