uva548

제목 설명:http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=19105

/* 1:             2:  getline sstream  ，     3:  getline sstream   */
#include <iostream>
#include <cstdio>
#include <sstream>
#include <string>

using namespace std;
const int maxn = 10000 + 1;

int in_order[maxn], post_order[maxn], lchild[maxn], rchild[maxn];   //lchild[i]  i      
int n;  //     
int best, best_sum;     //             

bool read_input(int * a) {
    string str;
    if(!getline(cin, str))  return false;   //getline stringstream
    stringstream ss(str);   n = 0;
    int val;
    while(ss >> val)    a[n++] = val;
    return n > 0;
}

int make_tree(int start1, int end1, int start2, int end2) {
    if(start1 > end1)   return 0;

    int root = post_order[end2];

    int p = start1;
    while(in_order[p] != root)  p++;
    int lchild_num = p - start1;    //         

    lchild[root] = make_tree(start1, p-1, start2, start2 + lchild_num - 1);
    rchild[root] = make_tree(p+1, end1, start2 + lchild_num, end2-1);   //       
    return root;
}

void dfs(int node, int sum) {   //   node           ，                     sum 
    sum += node;    //               
    if(!lchild[node] && !rchild[node]) {
        if((sum < best_sum) || (sum == best_sum && node < best)) {  //              
            best_sum = sum;
            best = node;
        }
    }
    if(lchild[node])    dfs(lchild[node], sum);
    if(rchild[node])    dfs(rchild[node], sum);
}

int main()
{
    while(read_input(in_order)) {
        read_input(post_order);     //           
        make_tree(0, n-1, 0, n-1);      //               
        best_sum = 100000;
        dfs(post_order[n-1], 0);    //        ，          0
        printf("%d
", best);
    }
    return 0;
}