UVA10410 树重建 Tree Reconstruction

· · 题解

由于我们只需要确定出父子关系，而一个父亲可能有多个儿子，但一个儿子只能有一个父亲。这启发我们从后往前遍历序列寻找。

我们知道，dfs遍历相比于bfs遍历更能体现父子关系，由此想到我们以dfs序列为核心、bfs序列做辅助来做这道题。

我们回顾dfs和bfs的性质，结合题目描述。对于结点 u 和 u 的儿子 v，不难得到以下结论

bfs序列

… 、u、 深度和 u 相同且权值大于 u 的结点 、 深度和 v 相同且父亲的权值小于 u 的结点 、v_1、v_2、…

dfs序列

… 、 u 、v_1、v_1的子树 、v_2、v_2的子树 、 …

其中，v_1 的权值小于 v_2 的权值。

我们考虑当前处理到结点 v 。

我们在dfs序列中从结点v向前遍历，我们找到第一个结点 u，满足 u 的bfs序小于 v 的bfs序。

根据上面的表格，我们可以推断出，u 只能是 v 的父亲或权值小于 v 的兄弟。

思考可以得到，当 u 的bfs序与 v 的bfs序相差大于1时，u 一定是 v 的父亲。

那么当 u 的bfs序和 v 的bfs序列相差等于1时呢？

如果 u 的权值大于 v，那 u 也一定是 v 的父亲。因为题目规定先访问权值更小的儿子。

如果 u 的权值小于 v，假设 u 是 v 的父亲，则需满足不存在“深度和 u 相同且权值大于 u 的结点”和“深度和 v 相同且父亲的权值小于 u 的结点”的结点。画图可以知道，满足这种情况时， u 是 v 的父亲或兄弟都是满足题意的。又因为 u 一定是 v 的父亲或者兄弟，所以我们在任何条件下认为 u 是 v 的兄弟都是没有矛盾的。

另外需要注意根结点的特殊处理，因为根结点是不可能有兄弟的。

Code：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1001;
int n;
int D[maxn],B[maxn];
int bfn[maxn];
vector <int> S[maxn];
int ne[maxn];

void init(){
    memset(D,0,sizeof(D));
    memset(B,0,sizeof(B));
    memset(bfn,0,sizeof(bfn));
    memset(ne,0,sizeof(ne));
    for(int i=1;i<=1000;++i)S[i].clear();
}
void work(){
    for(int i=1;i<=n;++i){
        cin>>B[i];
        bfn[B[i]]=i;
    }
    for(int i=1;i<=n;++i){
        cin>>D[i];
    }
    for(int i=n;i>=1;--i){
        int v=D[i];
        for(int j=i-1;j>=1;--j){
            int u=D[j];
            if((bfn[u]==bfn[v]-1)&&u<v){
                ne[u]=v;
                break;
            }
            if(bfn[u]<=bfn[v]-1){
                S[u].push_back(v);
                break;
            }
        }   
    }
    if(!S[D[1]].size())S[D[1]].push_back(D[2]);
    for(int i=1;i<=n;++i){
        printf("%d:",i);
        if(S[i].size()){
            for(int t=ne[S[i][0]];t;t=ne[t]){
                S[i].push_back(t);
            }
        }
        sort(S[i].begin(),S[i].end());
        for(int p=0;p<S[i].size();++p){
            printf(" %d",S[i][p]);
        }
        printf("\n");
    }
}
int main(){
    while(cin>>n){
        init();
        work();
    }
    return 0;
}