B. 完全二叉树
时间限制: 1000ms
空间限制: 262144KB
Time Limit Exceeded
55 分
题目描述
定义一棵树是合法的，当且仅当能通过若干次交换一个结点的左右儿子（可以交换空结点），使其成为一棵完全二叉树。
给定一棵根为1的n个点的二叉树。
你可以进行若干次以下三种操作：
删除一个叶子结点（不包括根结点）。
给一个没有左儿子的结点插入一个左儿子。
给一个没有右儿子的结点插入一个右儿子。
问使给定的树变成合法的最小操作次数。
n<=1e6
我写的是线段树（已经被迫非递归建树了）
O(n)
#include<bits/stdc++.h>
using namespace std;
int n,a[22][2000010],dep[1000010],deep[1000010],ls[1000010],rs[1000010];
inline int min(int x,int y)
{
return x>y?y:x;
}
inline int max(int x,int y)
{
return x>y?x:y;
}
void dfs(int fa,int p,int id)
{
dep[p]=dep[fa]+1;
deep[dep[p]]++;
if((id-(1<<dep[fa])+1)<=2000005)
a[dep[p]][id-(1<<dep[fa])+1]=1;
if(ls[p]!=0)
dfs(p,ls[p],2*id);
if(rs[p]!=0)
dfs(p,rs[p],2*id+1);
return;
}
int sum[4000010],ans[4000010],l[4000010],r[4000010],lc,rc,mid,x,y;
void build(int id)
{
x=1<<id-1;
y=1<<id;
for(int i=x;i<y;i++)
sum[i]=a[id][i-x+1],ans[i]=0,l[i]=r[i]=i-x+1;
for(int i=x-1;i>=1;i--)
{
lc=i<<1;
rc=i<<1|1;
sum[i]=sum[lc]+sum[rc];
l[i]=l[lc];
r[i]=r[rc];
mid=l[i]+r[i]>>1;
ans[i]=min(min(ans[rc]+sum[lc],r[i]-mid-sum[rc]+ans[lc]),min(ans[lc]+sum[rc],mid-l[i]+1-sum[lc]+ans[rc]));
}
return;
}
int main()
{
//ios::sync_with_stdio(false);
//cin.tie(0);
//cout.tie(0);
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d %d",&ls[i],&rs[i]);
}
dfs(0,1,1);
for(int i=1;i<=n;i++)
{
deep[i]+=deep[i-1];
}
int aans=1e9;
for(int i=1,j=1;j<=n;i++,j<<=1)
{
build(i);
aans=min(aans,ans[1]+j-1-deep[i-1]+n-deep[i]);
}
printf("%d",aans);
return 0;
}