不知道为啥MLE了,是因为1多了dp太深吗
#include <bits/stdc++.h>
using namespace std;
int data[500010][3],num=0,min1[500010][3],max1[500010][3],ansmax=-1,ansmin=500010;
char tree[500010];
void build_tree(){
int now=num;
if(tree[num]=='1'){
data[num][0]=1;
data[num][1]=++num;
build_tree();
}
if(tree[num]=='2'){
data[num][0]=2;
data[num][1]=++num;
build_tree();
data[now][2]=++num;
build_tree();
}
return ;
}
void dp(int i,int m){
if(min1[i][m]==-1){
for(int j=1;j<=data[i][0];++j)for(int k=0;k<3;++k)if(k!=m)dp(data[i][j],k);
int ans=500010;
if(data[i][0]==0)ans=0;
if(data[i][0]==1)for(int k=0;k<3;++k)if(k!=m)ans=min(ans,min1[data[i][1]][k]);
if(data[i][0]==2){
if(m==0)ans=min(min1[data[i][1]][1]+min1[data[i][2]][2],min1[data[i][1]][2]+min1[data[i][2]][1]);
if(m==1)ans=min(min1[data[i][1]][0]+min1[data[i][2]][2],min1[data[i][1]][2]+min1[data[i][2]][0]);
if(m==2)ans=min(min1[data[i][1]][1]+min1[data[i][2]][0],min1[data[i][1]][0]+min1[data[i][2]][1]);
}
if(m==1)ans++;
min1[i][m]=ans;
}
if(max1[i][m]==-1){
for(int j=1;j<=data[i][0];++j)for(int k=0;k<3;++k)if(k!=m)dp(data[i][j],k);
int ans=-1;
if(data[i][0]==0)ans=0;
if(data[i][0]==1)for(int k=0;k<3;++k)if(k!=m)ans=max(ans,max1[data[i][1]][k]);
if(data[i][0]==2){
if(m==0)ans=max(max1[data[i][1]][1]+max1[data[i][2]][2],max1[data[i][1]][2]+max1[data[i][2]][1]);
if(m==1)ans=max(max1[data[i][1]][0]+max1[data[i][2]][2],max1[data[i][1]][2]+max1[data[i][2]][0]);
if(m==2)ans=max(max1[data[i][1]][1]+max1[data[i][2]][0],max1[data[i][1]][0]+max1[data[i][2]][1]);
}
if(m==1)ans++;
max1[i][m]=ans;
}
}
int main(){
freopen("test.in","r",stdin);
scanf("%s",&tree);
build_tree();
memset(min1,-1,sizeof(min1));
memset(max1,-1,sizeof(max1));
for(int k=0;k<3;++k)dp(0,k);
for(int k=0;k<3;++k){
ansmin=min(ansmin,min1[0][k]);
ansmax=max(ansmax,max1[0][k]);
}
printf("%d %d",ansmax,ansmin);
return 0;
}