题解：P2274 [HNOI2002] 树的排序

Kaf_yoU · 2025-11-25 09:17:20 · 题解

蒟蒻瑟瑟发抖。真的有紫吗？

upd：根据原首篇题解，对文中的一些解释作了修改。

题意简述：

对于所有二叉树都给其定义一个编号，具体规则如下：

空树编号为 0，只有根节点的树编号为 1；
设 m 为一任意非负整数，那么任意一棵有 m 个节点的树的编号小于任意一棵有 m+1 个节点的树；
设 A,B 是两棵节点数相同的树（A,B 不相同），则 A 编号比 B 小时，一定满足下面两个条件之一（反之亦然）：
编号按照正常的规则，编号应是连续的非负整数，任意一棵树唯一对应一个编号，任意一个非负整数唯一对应一棵树。

注：上文中的树均指二叉树。

给定一棵树的编号 n，求出该树的形态；具体表示法形如：

如果是一个结点的二叉树，则输出 X；
如果二叉树的左、右子树分别为 L 和 R，L,R 的输出形式分别为 L' 和 R'，则输出为 \texttt{(}L'\texttt{)}X\texttt{(}R'\texttt{)}，当左子树为空时，输出为 X\texttt{(}R'\texttt{)}，当左子树为空时 \texttt{(}L'\texttt{)}X。

下面设题目给的编号为 \text{id} 而不是 n，n 一般用于代指点数。

一眼叉掉枚举所有二叉树。

根据编号分配的第二条规则，只有当前面的编号分配给所有节点数为 1\sim n-1 的二叉树时才能开始给节点数为 n 的二叉树分配编号。

所以需要先得到节点数为 1\sim n-1 的的不同二叉树数量。

设 h(n) 表示 n 个节点的本质不同二叉树的数量；推递推式，注意到除了根节点以外左子树和右子树的节点数之和一定是 n-1，则左子树可以放 l\in[0,n-1] 个节点，右子树则放 r=n-1-l 个节点，分别取出这两种节点数的方案，得到递推式：

h(n)=\sum_{i=0}^{n-1}h(i)h(n-1-i)

Tips：该式事实上就是卡特兰数的递推式，这里挂个 OI-wiki 的链接。

从输出的格式来看递归很好写，考虑直接 DFS 求出答案字符串；设当前要求 n 个点，编号为 \text{id} 的树形态。

当 n=0 或 n=1 时，为题面里的第一种情况，依题意返回空串 / 单个字符 \texttt{X}。

否则，找出左子树和右子树对应的节点数与形态编号，按格式拼接在一起（若有空树则忽视）。

求子树信息过程

节点数

上文提出，左子树和右子树的节点数之和一定，先仅考虑左子树。

暴枚一下发现上文的那个求形态的递推式（卡特兰数）增长非常快，在 20 项上下时就会超出 5\times 10^8（即题目 \text{id} 值域），所以考虑暴力枚举左子树的节点数判断合法性。

枚举 l\in[0,n-1] 作为左子树大小，l>0 时前面所有小于该情况的编号之和为所有左子树大小比当前情况小的二叉树数，即 \sum\limits_{i=0}^{l-1}h(i)h(n-i-1)。可以拿个变量递推前缀和。

请尝试仔细理解上式；当上式大于当前树编号 \text{id} 时显然不合法，根据题面编号分配的规则 3，使上式合法的最大 l 即左子树大小，对应的右子树大小为 r=n-l-1。

编号

求出节点数后继续观察第三条规则，这个比较方法非常像整数从高位向低位的比较；将整棵树的编号看作一个 h(r) 进制的两位数，高位为左子树编号，低位为右子树编号（应忽略根节点）；
至于为什么基数是右子树的种类，请自行思考。

得到当前树的编号为 {\color{red}\text{id}}= 左子树编号 \times \ h(r)\ + 右子树编号，注意此处 {\color{red}\text{id}} 为在左子树大小 =l 时使左子树编号加至目标状态的次数（从 \mathbf{0} 开始），去掉前面的 l 后等于实际 \text{id}-\sum\limits_{i=0}^{l-1}h(i)h(n-i-1)。下文中这个处理后的 {\color{red}\text{id}} 使用红色标出。

综上，左子树编号为 \lfloor\dfrac{{\color{red}\text{id}}-1}{h(r)}\rfloor+1，右子树编号为 ({\color{red}\text{id}}-1) \bmod h(r)+1。

不对啊，按理来说分母 \color{red}\text{id} 无需减 1，最终编号无需加 1，为啥要这么写啊？

解释一下，由于算出来的是左 / 右子树从空树开始变换至目标状态的次数，而空树编号从 0 开始；减 1 和加 1 都基于该原理。

对于初始给的 \text{id}，照样处理传入即可。

边界什么的各种细节不少。

Think twice, code once.

#include <bits/stdc++.h>
using namespace std;
typedef long long i64;

const int V = 22 + 1;
string ans;
i64 h[V];
int id;

void init_cat (int n)
{
    h[0] = h[1] = 1;
    for (int i = 2; i <= n; i ++)
        for (int j = 1; j <= i; j ++)
            h[i] += h[j - 1] * h[i - j];
}

string prt (int n, i64 id)
{
    if (!n) return "";
    if (n == 1) return "X";

    int lnd = 0, rnd = n - 1; i64 lid = 0;
    while (lid + h[lnd] * h[rnd] < id)
        lid += h[lnd] * h[rnd], lnd ++, rnd --;

    string res = "";
    if (lnd) res += '(' + prt (lnd, (id - lid - 1) / h[rnd] + 1) + ')';
    res += 'X';
    if (rnd) res += '(' + prt (rnd, (id - lid - 1) % h[rnd] + 1) + ')';
    return res;
}

int main ()
{
    init_cat (V - 1);
    cin >> id;
    int rot = 1; i64 rid = 0;
    while (rid + h[rot] < id) rid += h[rot], rot ++;
    cout << prt (rot, id - rid);
    return 0;
}

若有更合理的细节解释请指出！（鞠躬）

有借鉴 @AFO_Song 佬的题解与 @SUPERLWR 佬的题解，可以算对其一定的补充说明？