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： ```cpp #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; } ```