记录编号	420723	评测结果	AAAAA
题目名称	[UVa 548] 树	最终得分	100
用户昵称	不需要黄桃	是否通过	通过
代码语言	C++	运行时间	0.002 s
提交时间	2017-07-05 14:54:55	内存使用	0.48 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
string midd,aftt;
bool son[10010];
int im[10010],fa[10010],dad[10010],aa[10010],js,ans,minn=10002,j,maxx=0;
int wer;
void fz(int kk[],int pp[],int qd,int zd,int dd)
{
	if(dd==1)
		for(int i=qd;i<zd;i++)
			kk[i]=pp[i];
	else
		for(int i=qd;i<zd;i++)
			kk[i-qd+1]=pp[i];
}
void buildd(int s1[],int s2[],int ro)
{
	if(s1[0]>=1)
	{
		int fat=s2[s2[0]],po;
		dad[fat]=ro;son[ro]=1;
		if(s1[0]>1)
		{
			int sm[10010],sa[10010];
			for(int i=1;i<=s2[0];i++)
				if(s1[i]==fat)
				{
					po=i;
					break;
				}
			if(po<=10000)
				fz(sm,s1,1,po,1);
			sm[0]=po-1;
			if(po<=10000)
				fz(sa,s2,1,po,1);
			sa[0]=po-1;
			buildd(sm,sa,s2[s2[0]]);
			memset(sm,0,sizeof(sm));
			memset(sa,0,sizeof(sa));
			if(po<=10000)
				fz(sm,s1,po+1,s1[0]+1,0);
			sm[0]=s1[0]-po;
			if(po<=10000)
				fz(sa,s2,po,s2[0],0);
			sa[0]=s1[0]-po;
			buildd(sm,sa,s2[s2[0]]);
		}
	}
}
void read(string k)
{
	int x=0;js=0;
	memset(aa,0,sizeof(aa));
	for(int i=0;i<k.length();i++)
	{
		if(k[i]>='0'||k[i]<='9')
		{
			x=0;
			while(k[i]>='0'&&k[i]<='9'&&i<k.length())
			{
				x=x*10+k[i]-'0';
				i++;
			}
			if(js<=10000)
				aa[++js]=x;
			if(x>maxx)
				maxx=x;
		}
	}
}
int main()
{
	freopen("sumtree.in","r",stdin);
	freopen("sumtree.out","w",stdout);
	while(getline(cin,midd),getline(cin,aftt))
	{
		if(midd[0]>='0'&&midd[0]<='9')
		{
			memset(dad,0,sizeof(dad));
			memset(son,0,sizeof(son));
			memset(im,0,sizeof(im));
			memset(fa,0,sizeof(fa));
			minn=10002;
			wer=0;
			read(midd);
			if(js<=10000)
				for(int i=1;i<=js;i++)
					im[i]=aa[i];
			im[0]=js;
			read(aftt);
			if(js<=10000)
				for(int i=1;i<=js;i++)
					fa[i]=aa[i];	
			fa[0]=js;
			buildd(im,fa,9999);
			int i;
			for(i=1;i<=maxx&&i<=10000;i++)
			{
				if(!son[i]&&dad[i])
				{
					j=i;ans=0;
					while(j!=9999)
					{
						ans+=j;
						j=dad[j];
					}
					if(ans<minn)
					{
						wer=i;
						minn=ans;
					}
				}
			}
			cout<<wer<<endl;
		}
	}
	return 0;
}