2477.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"iostream.h"
#include"stdio.h"
struct tree
{
	int l,r;
	__int64 value;
	int child;
}t[100];
int n,root;
bool init()
{
	int i,times[100];
	cin>>n;
	if(n==0) return 0;
	for(i=1;i<=n;i++)
		times[i]=0;
	for(i=1;i<=n;i++)
	{
		cin>>t[i].l>>t[i].r;
		if(t[i].l>0)
			times[t[i].l]++;
		if(t[i].r>0)
			times[t[i].r]++;
	}
	for(i=1;i<=n;i++)
		if(times[i]==0)
		{
			root=i;
			break;
		}

	return 1;
}
const __int64 maxvalue=(__int64)1<<60;
int travel(int a)
{
	if(a<=0)return 0;
	
	t[a].child=travel(t[a].l)+travel(t[a].r)+1;

	return t[a].child;
}
void great(int s,__int64 value)
{
	t[s].value=value;
	
	if(t[s].l>0)
		great(t[s].l,value/2/t[s].child*t[t[s].l].child);
	if(t[s].r>0)
		great(t[s].r,value/2/t[s].child*t[t[s].r].child);

	return ;
}
int main()
{
	int i;
	while(init())
	{
		travel(root);
		great(root,maxvalue);
		for(i=1;i<=n;i++)
		{
			printf("%I64d",t[i].value);
			if(i<n)printf(" ");
		}
		printf("\n");
	}
	return 0;
}