记录编号	422055	评测结果	AAAAA
题目名称	[UVa 548] 树	最终得分	100
用户昵称	fate1	是否通过	通过
代码语言	C++	运行时间	0.001 s
提交时间	2017-07-08 20:12:27	内存使用	0.44 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
int mid[10001],las[10001],father[10001],minl=999999999,jl=0,jk,ww=999999999;
bool flag[10001]={false};
void find(int lm,int rm,int ll,int rl)
{
	int qq;
	if(lm==rm)
	{
		if(mid[lm]<ww)
			ww=mid[lm];
		flag[rm]=true;
		return ;
	}
	for(int i=lm;i<=rm;i++)
	{
		if(mid[i]==las[rl])
			qq=i;
	}
	flag[qq]=true;
	if(qq-1>=lm)
	{
		for(int i=lm;i<=qq-1;i++)
		{
			father[i]+=mid[qq];
		}
	    find(lm,qq-1,ll,ll+(qq-1-lm));
	}
	if(qq+1<=rm&&flag[qq+1]==false)
	{
		for(int i=qq+1;i<=rm;i++)
		{
			father[i]+=mid[qq];
		}
	    find(qq+1,rm,rl-1-(rm-qq-1),rl-1);
	}
}
using namespace std;
int main()
{
	freopen("sumtree.in","r",stdin);
	freopen("sumtree.out","w",stdout);
	string z,h;
	while(getline(cin,z),getline(cin,h))
	{
		for(int i=0;i<=10001;i++)
		{
			flag[i]=false;
		}
		minl=999999999;
		ww=999999999;
		jl=0;
		int ans=0;
		int qqq=0;
		for(int i=0;i<=z.size()-1;i++)
		{
			if(z[i]>='0'&&z[i]<='9')
			{
				if(ans==0)
					ans+=z[i]-'0';
				else
				{
					ans*=10;
					ans+=z[i]-'0';
				}
			}
			if(z[i]==' ')
			{
				mid[qqq]=ans;
				ans=0;
				qqq++;
			}
		}
		mid[qqq]=ans;
		for(int i=0;i<=qqq;i++)
			father[i]=mid[i];
		ans=0;
		qqq=0;
		for(int i=1;i<=h.size()-1;i++)
		{
			if(h[i]>='0'&&h[i]<='9')
			{
				if(ans==0)
					ans+=h[i]-'0';
				else
				{
					ans*=10;
					ans+=h[i]-'0';
				}
			}
			if(h[i]==' ')
			{
				las[qqq]=ans;
				ans=0;
				qqq++;
			}
		}
		las[qqq]=ans;
		find(0,qqq,0,qqq);
		for(int i=0;i<=qqq;i++)
		{
			if(father[i]<minl)
			{
				minl=father[i];
				jl++;
				jk=i;
			}
		}
		if(jl==1)
			cout<<minl<<endl;
		else
		{	
			cout<<ww<<endl;
		}
	}
}