洛谷 P3621 [APIO2007]风铃【贪心】

没有算法，但是要注意细节。

首先无解的情况，显然的是最小深度的叶子节点和最大深度的叶子节点的深度差大于1；还有一种比较难想，就是如果一个点的左右子树都有最大和最小深度的叶子节点，这样交换左右子树也不行。

答案比较容易，就是统计一下右子树size>左子树size的节点个数即可。

#include<iostream>

#include<cstdio>

using namespace std;

const int N=200005;

int n,h[N],cnt,tot,c[N][2],fa[N],si[N],de[N],mx[N],mn[N];

bool fl,v[N];;

int read()

{

	int r=0,f=1;

	char p=getchar();

	while(p<'0'||p>'9')

	{

		if(p=='-')

			f=-1;

		p=getchar();

	}

	while(p>='0'&&p<='9')

	{

		r=r*10+p-48;

		p=getchar();

	}

	return r*f;

}

void dfs(int u)

{

	if(u>n)

	{

		mn[u]=de[u],mx[u]=de[u];

		return;

	}

	for(int i=0;i<=1;i++)

	{

		de[c[u][i]]=de[u]+1;

		dfs(c[u][i]);

		si[u]+=si[c[u][i]];

	}

	mn[u]=min(mn[c[u][0]],mn[c[u][1]]);

	mx[u]=max(mx[c[u][0]],mx[c[u][1]]);

	if(mn[u]!=mx[u])

		v[u]=1;

	if(v[c[u][0]]&&v[c[u][1]])

		fl=1;

}

int wk(int u)

{

	if(u>n)

		return 0;

	return (si[c[u][1]]>si[c[u][0]])+wk(c[u][0])+wk(c[u][1]);

}

int main()

{

	n=read();

	tot=n;

	for(int i=1;i<=n;i++)

	{

		c[i][0]=read(),c[i][1]=read();

		if(c[i][0]==-1)

			c[i][0]=++tot,si[c[i][0]]=1;

		if(c[i][1]==-1)

			c[i][1]=++tot,si[c[i][1]]=1;

	}

	de[1]=1;

	dfs(1);//cerr<<mn<<" "<<mx<<endl;

	if(mx[1]-mn[1]>1||fl)

	{

		puts("-1");

		return 0;

	}

	printf("%d\n",wk(1));

	return 0;

}

巴特西

洛谷 P3621 [APIO2007]风铃【贪心】

最新文章

热门文章