记录编号	247122	评测结果	AAAAA
题目名称	[UVa 548] 树	最终得分	100
用户昵称	Fmuckss	是否通过	通过
代码语言	C++	运行时间	0.002 s
提交时间	2016-04-08 09:48:43	内存使用	0.50 MiB

#include<iostream>
#include<cstdio> 
#include<math.h>
#include<string>
#include<string.h>
using namespace std;
const int maxn = 1e4+10;
const int inf = 1e9;

int mid[maxn];
int beh[maxn];
int pos[maxn];
int n;


inline int get_line(int *a) {
	int i = 0;
	char tmp;
	while(true) {
		tmp = getchar();
		int ans = 0;
		while(tmp < '0' || tmp > '9') {
			if(tmp == EOF) return false;
			tmp = getchar();
		}
		while(tmp <= '9' && tmp >= '0') {
			ans = ans*10 + tmp - '0';
			tmp = getchar();
		}
		a[++i] = ans;
		if(tmp == '\n' || tmp == '\r') return i;
	}
}


class tree {
private:
	struct node {
		int lc, rc;
		inline node() {}
		inline node(int lc_, int rc_) { lc = lc_, rc = rc_; }
	}ns[maxn];
	int nowmax;
	int nownum;
public:
	inline void init() {
		nowmax = inf;
		nownum = 0;
	}
	inline int build(int ml, int mr, int bl, int br) {
		if(mr < ml) return 0;
		if(ml == mr) return mid[ml];
		int now_root = beh[br];
		int p = pos[now_root];
		//int sizel = p-ml;
		//int sizer = mr-p;
		ns[now_root] = node(build(ml, p-1, bl, bl + (p-ml-1)), 
							build(p+1, mr, br - (mr-p), br-1));
		return now_root;
	}
	inline void dfs(int now, int v) {
		if(!ns[now].lc && !ns[now].rc) {
			if(v < nowmax) {
				nownum = now;
				nowmax = v;
			} else if(v == nowmax) {
				if(now < nownum) {
					nownum = now;
				}
			}
		}
		if(ns[now].lc) dfs(ns[now].lc, v+ns[now].lc);
		if(ns[now].rc) dfs(ns[now].rc, v+ns[now].rc);
	}
	inline void solve() {
		int root = build(1, n, 1, n);
		dfs(root, root);
		printf("%d\n", nownum);
	}
}t;


inline void get_pos() {
	for(int i = 1; i <= n; i++) {
		pos[mid[i]] = i;
	}
}


inline bool read() {

	n = get_line(mid);
	if(n) {
		get_line(beh);
		get_pos();
		return true;
	}
	return false;
}


int main(){
	freopen("sumtree.in", "r", stdin);
	freopen("sumtree.out", "w", stdout);
	while(read()) {
		t.init();
		t.solve();
	}
	return 0;
}