学了一下dfs建树
指针蛮好的,而且因为是dfs序直接倒着来就行了,和上司那个题差不多
#include<bits/stdc++.h> using namespace std; char ch[501000]; int sn[501000][5],root,f[501000],g[501000],it; void dfs(int &t) { t=++it; int x=ch[it]-'0'; if(x==0)return ; if(x==1)dfs(sn[t][1]); if(x==2)dfs(sn[t][1]),dfs(sn[t][2]); } int main() { scanf("%s",ch+1); int len=strlen(ch+1); dfs(root); for(int i=len;i>=1;i--) { f[i]=g[sn[i][1]]+g[sn[i][2]]+1; g[i]=max(f[sn[i][1]]+g[sn[i][2]],g[sn[i][1]]+f[sn[i][2]]); } cout<<max(f[1],g[1])<<" "; for(int i=len;i>=1;i--) { f[i]=g[sn[i][1]]+g[sn[i][2]]+1; g[i]=min(f[sn[i][1]]+g[sn[i][2]],g[sn[i][1]]+f[sn[i][2]]); } cout<<min(f[1],g[1]); }