https://contest.xinyoudui.com/contest/235/problem/1243

代码 40 分求调：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
int siz[maxn],dep[maxn];
int x[maxn],y[maxn];
int dp[maxn][2];
void dfs(int u,int fath){
	dep[u]=dep[fath]+1;
	if(x[u]) dfs(x[u],u);
	if(y[u]) dfs(y[u],u);
}
void solve(int u,int temp){
	if(x[u]) solve(x[u],temp),siz[u]+=siz[x[u]];
	if(y[u]) solve(y[u],temp),siz[u]+=siz[y[u]];
	if(dep[u]==temp){	
		if(!x[u]&&!y[u]){
			dp[u][0]=0; dp[u][1]=2; siz[u]=0;
		} 
		else if(!x[u]||!y[u]){
			dp[u][0]=0; dp[u][1]=1; siz[u]=1;
		}
		else{
			dp[u][0]=0; dp[u][1]=0; siz[u]=2;
		}
	} else {
		if(!x[u]) dp[x[u]][1]=(1<<(temp-dep[u]-1));
		if(!y[u]) dp[y[u]][1]=(1<<(temp-dep[u]-1));
		int temp1=dp[x[u]][1]+dp[y[u]][0];
		int temp2=dp[y[u]][1]+dp[x[u]][0];
		int temp3=dp[x[u]][0]+siz[y[u]];
		int temp4=dp[y[u]][0]+siz[x[u]];
		dp[u][0]=min(min(temp1,temp2),min(temp3,temp4));
		dp[u][1]=(1<<temp)-1-siz[u];
	}
}
int main(){
	int n;scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d%d",x+i,y+i);
	dfs(1,0); int ansmin=n-1;
	for(int i=1;i<=20;i++){
		int cnt=0,ans=0;
		for(int j=1;j<=n;j++){
			if(dep[j]<=i) cnt++;
			if(dep[j]>i+1) ans++;
		}
		ans+=(1<<i)-1-cnt;
		memset(siz,0,sizeof(siz));
		for(int j=1;j<=n;j++) dp[j][0]=dp[j][1]=1e9;
		solve(1,i); ans+=min(dp[1][0],dp[1][1]);
//		printf("                %d\n",ans);
		ansmin=min(ansmin,ans);
	}
	printf("%d\n",ansmin); return 0;
}