Gioush OJ
⌕ 题目搜索注册登录
← 返回题解列表

P1078 何处是归途 官方题解

Gioush OJ · 何处是归途 · 2026/09/07 00:00

【部分分：测试点 1∼41\sim 41∼4】

  • 按照给出的顺序建出原来的二叉查找树。
  • 枚举 1∼n1\sim n 的所有排列，分别建树，并与原树比较左右儿子关系。
  • 在所有能够建出同一棵树的排列中取字典序最小值。
  • 时间复杂度为 O(n! n2)\mathcal O(n!\,n^2)。

【部分分：测试点 5∼95\sim 95∼9】

  • 枚举排列的瓶颈同样来自方案数。先判断哪些安装顺序能够复原同一棵树。

  • 必要性很直接：一个结点只有在所有祖先已经出现以后，才能沿着正确的查找路径到达自己的位置。

  • 反过来，若每个结点都晚于自己的祖先出现，那么插入它时，所有祖先已经存在，而它的后代尚未出现。

  • 它会沿着原树中从根到自己的路径移动，因此一定落在原来的位置。这就证明了条件的充分性。

  • 根必须最先出现。根确定以后，左子树中的所有编号都小于右子树中的所有编号。

  • 因而字典序最小的顺序一定先复原左子树，再复原右子树。对子树递归使用同样的结论，得到的正是先序遍历。

  • 先序遍历中，祖先总在后代之前，所以它确实能够复原原树。由此既得到合法性，也得到字典序最小性。

  • 这一档可以朴素插入所有编号，再输出先序遍历。最坏时间复杂度为 O(n2)\mathcal O(n^2)，空间复杂度为 O(n)\mathcal O(n)。

【部分分：测试点 10∼1510\sim 1510∼15】

  • 这一档保证最终树高不超过 5050。
  • 沿用上一档的建树过程。朴素插入一个编号时，访问的结点数不超过树高 hh。
  • 因此建树时间复杂度为 O(nh)\mathcal O(nh)，在本档中可以写作 O(n)\mathcal O(n)。
  • 先序遍历仍为线性复杂度。

【正解】

  • 朴素插入的瓶颈在于反复沿树向下查找。考虑直接从安装顺序恢复树形。

  • 记 pip_i 为编号 ii 在原安装顺序中出现的位置。二叉查找树的中序遍历固定为 1,2,…,n1,2,\ldots,n。

  • 对任意一棵子树，它包含的编号构成连续区间。区间中最早安装的编号会先占据子树根的位置，因此根的 pip_i 最小。

  • 所以原树满足：中序次序为编号顺序，并且父亲的 pip_i 小于儿子的 pip_i。这正是以下标为键、以 pip_i 为优先级的最小笛卡尔树。

  • 反过来，上述两条性质能够唯一确定一棵树：根只能是整个区间中 pip_i 最小的编号，左右区间再递归确定左右子树。

  • 这与二叉查找树的递归结构完全相同，因此构造这棵笛卡尔树就能得到原树。

  • 接下来只需在线性时间内构造笛卡尔树。按编号 1,2,…,n1,2,\ldots,n 扫描，用单调栈维护当前树的右链，栈内 pip_i 严格递增。

  • 处理编号 ii 时，令 xx 为当前栈顶。只要 px>pip_x>p_i，就弹出 xx 并继续比较。最后一个弹出的结点成为 ii 的左儿子。

  • 弹栈结束后，若栈不空，则 ii 成为当前栈顶的右儿子。随后把 ii 压入栈中，新的右链仍满足单调性。

  • 扫描结束后，栈底就是整棵树的根。输出这棵树的先序遍历即可。

  • 每个结点只进栈、出栈一次，建树与遍历的总时间复杂度为 O(n)\mathcal O(n)，空间复杂度为 O(n)\mathcal O(n)。

【参考代码】

/*Author:EhundateghDate:2026/8/31Name:path.cppYou steal,I kill.*/#include <cstdio>#include <cstring>#include <algorithm>#define MAXN 200010using namespace std; int c,T,n,Pos[MAXN],ls[MAXN],rs[MAXN],S[MAXN],Tail;bool First; void Print(int Now){    if(!Now) return;    if(!First) putchar(' ');    First=false;printf("%d",Now);    Print(ls[Now]);Print(rs[Now]);    return;} void Solve(){    scanf("%d",&n);Tail=0;    for(int i=1;i<=n;i++){        int In1;scanf("%d",&In1);Pos[In1]=i;        ls[i]=rs[i]=0;    }    for(int i=1;i<=n;i++){        int Last=0;        while(Tail&&Pos[S[Tail]]>Pos[i]) Last=S[Tail--];        if(Tail) rs[S[Tail]]=i;        ls[i]=Last;S[++Tail]=i;    }    First=true;Print(S[1]);putchar('\n');    return;} int main(){    freopen("path.in","r",stdin);    freopen("path.out","w",stdout);    scanf("%d%d",&c,&T);    while(T-->0) Solve();    return 0;}