题意：

给出两个二叉树的DFS序列，输出每个结点的父结点编号。

思路：

我快要gg了…

知道要怎么做就是不知道怎么写…

真的…菜得一逼…递归都不会写（。

看题解写完就…情绪低落（。

容易知道如果之后一个结点相同，则说明这一定是当前结点的子结点；如果不同，说明这两个都是该结点的子结点，找到这两个结点分别在两个序列里的位置，然后递归下去。

考虑一个栗子：

1 2 4 7 8 9 5 3 6

1 2 5 4 7 8 9 3 6

4和5找到以后，3 6要怎么办呢？要把3当成1的子结点才行，所以这里要往上爬一下。

关于栗子的解释可以见代码。

这里有一个点很奇怪，son[0]如果为1的话，会TLE，但是如果为2就AC了，超时肯定是while(!son[fa])那里循环不出来了，但是不应该只有一个根结点吗？很奇怪，等下再想想。

update：注意这里while(!son[fa])fa=far[fa];如果son[0]设为1的话，如果son[0]=0了就循环不出来了，所以一定要设为2。

代码：

typedef long long ll;
int a[100010],b[100010];
int hsa[100010],hsb[100010];
bool vis[100010];
int far[100010],son[100010];
int n;
void dfs(int al,int ar,int bl,int br,int fa)
{
    //printf("%d,%d,%d,%d,%d\n",al,ar,bl,br,fa);
    if(al>ar||bl>br||ar>n||br>n)return;
    if(a[al]==b[bl])
    {
        if(vis[a[al]])return;
        far[a[al]]=fa;
        son[fa]--;
        vis[a[al]]=true;
        dfs(al+1,ar,bl+1,br,a[al]);
    }
    else
    {
        int la=hsa[b[bl]]-al;
        int lb=hsb[a[al]]-bl;
        //printf("[%d,%d]\n",hsa[b[bl]],hsb[a[al]]);
        dfs(al,al+la-1,hsb[a[al]],hsb[a[al]]+la-1,fa);//(3,6,4,7,2)
        dfs(hsa[b[bl]],hsa[b[bl]]+lb-1,bl,bl+lb-1,fa);//(7,7,3,3,2)
        //printf("[%d]\n",son[fa]);
        while(!son[fa])fa=far[fa];
        dfs(al+la+lb,ar,bl+la+lb,br,fa);//(8,9,8,9,1)
    }
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            vis[i]=false;
            hsa[a[i]]=i;
            son[i]=2;
        }
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&b[i]);
            hsb[b[i]]=i;
        }
        son[0]=2;
        dfs(1,n,1,n,0);
        for(int i=1;i<n;i++)
            printf("%d ",far[i]);
        printf("%d\n",far[n]);
    }
    return 0;
}