记录编号	279720	评测结果	AAAAA
题目名称	[UVa 548] 树	最终得分	100
用户昵称	@@@	是否通过	通过
代码语言	C++	运行时间	0.001 s
提交时间	2016-07-09 16:13:49	内存使用	0.46 MiB

#include<iostream>
#include<cstdio>
#include<string>
#include<sstream>
#include<algorithm>
using namespace std;
const int maxv=10000+10;
int in_order[maxv],post_order[maxv],lch[maxv],rch[maxv];
int n;
bool read_list(int* a){
	string line;
	if(!getline(cin,line)) return false;
	stringstream ss(line);
	n=0;
	int x;
	while(ss>>x) a[n++]=x;
	return n>0;
}
int build(int L1,int R1,int L2,int R2){
	if(L1>R1) return 0;
	int root=post_order[R2];
	int p=L1;
	while(in_order[p]!=root) p++;
	int cnt=p-L1;
	lch[root]=build(L1,p-1,L2,L2+cnt-1);
	rch[root]=build(p+1,R1,L2+cnt,R2-1);
	return root;
}
int best,best_sum;
void dfs(int u,int sum){
	sum+=u;
	if(!lch[u] && !rch[u]){
		if(sum<best_sum||(sum==best_sum&&u<best)){
			best=u;best_sum=sum;
		}
	}		
	if(lch[u]) dfs(lch[u],sum);
	if(rch[u]) dfs(rch[u],sum);
}
int main(){
	freopen("sumtree.in", "r", stdin);
	freopen("sumtree.out", "w", stdout);
		while(read_list(in_order)){
			read_list(post_order);
			build(0,n-1,0,n-1);
			best_sum=1000000000;
			dfs(post_order[n-1],0);
			cout<<best<<"\n";
	}
	return 0;
}