记录编号	247035	评测结果	AAAAA
题目名称	[UVa 548] 树	最终得分	100
用户昵称	ZXCVBNM_1	是否通过	通过
代码语言	C++	运行时间	0.002 s
提交时间	2016-04-07 21:38:45	内存使用	0.46 MiB

#include<bits/stdc++.h>
using namespace std;
#define INF 1e9
int q1[10010],q2[10010],L[10010],R[10010],MIN,MINI;
int Build(int l1,int r1,int l2,int r2)
{
    if(l1>r1)return 0;
    int rt=q2[r2],i=l1,cnt;
    while(q1[i]!=rt)i++;
    cnt=i-l1;
    L[rt]=Build(l1,i-1,l2,l2+cnt-1);
    R[rt]=Build(i+1,r1,l2+cnt,r2-1);
    return rt;
}
void dfs(int k,int tot)
{
    if(L[k]==0&&R[k]==0)
    {
        if(tot<MIN)
        {
            MIN=tot;
            MINI=k;
        }
        else if(tot==MIN&&k<MINI)MINI=k;
        return;
    }
    if(L[k]!=0)dfs(L[k],tot+L[k]);
    if(R[k]!=0)dfs(R[k],tot+R[k]);
}
int main()
{
    freopen("sumtree.in","r",stdin);
    freopen("sumtree.out","w",stdout);
    int n,root,sum,i;
    char ch;
    while(scanf("%d",&q1[1])==1)
    {
        n=0;
        //memset(q1,0,sizeof(q1));
        //memset(q2,0,sizeof(q2));
        sum=0;
        ch=getchar();
        for(i=2;;i++)
        {
            if(ch=='\n'||ch=='\r')break;
            scanf("%d",&q1[i]);
            ch=getchar();
            //if(ch=='\n')break;
            /*scanf("%c",&ch);
            if(ch==' '){q1[++n]=sum;sum=0;}
            else if(ch>='0'&&ch<='9')sum=sum*10+(ch-'0');
            else break;*/
        }
        n=i-1;
        //if(sum!=0)q1[++n]=sum;
        //n=0;sum=0;
        //while(1)
        for(i=1;i<=n;i++)
        {
            scanf("%d",&q2[i]);
            ch=getchar();
            /*scanf("%c",&ch);
            if(ch==' '){q2[++n]=sum;sum=0;}
            else if(ch>='0'&&ch<='9')sum=sum*10+(ch-'0');
            else break;*/
        }
        //if(sum!=0)q2[++n]=sum;
        root=Build(1,n,1,n);
        MIN=INF;MINI=0;
        dfs(root,root);
        printf("%d\n",MINI);
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}