首先可以观察出一颗 \(n\) 个节点的二叉树，当其字典序最小的时候，其形态为一条向右偏的链，当其字典序最大的时候，是一条向左偏的链。
由于每一种编码对应唯一的一颗二叉树，我们可以先建树。
然后考虑树上分治，尝试以下三种方式：
-
变大右子树的字典序
-
变大左子树的字典序，并将右子树变成一条链
-
将左子树的大小 \(+1\) ，右子树的大小 \(-1\) ，然后都转化成一条向右偏的链
递归边界为 \(sz[u]==2\)
注意：当 \(n\) 个节点无解时，输出 \(n+1\) 个节点的树的最小字典序，即一条右偏链
顺便请求加强一下数据
Code
#include <bits/stdc++.h>
using namespace std;
const int N = 5000 + 5;
int a[N], ls[N], rs[N], sz[N], n = 0, tot = 0, w = 1;
vector<int> v[N]; //v[u]表示u这棵子树的字典序
void dfsp(int siz) { //建树
sz[++n] = siz;
if (siz == 1) return;
int lz = a[w + 1], rz = siz - a[w + 1] - 1, u = n;
if (lz >= 1) {ls[u] = n + 1; if (lz > 1) ++w; dfsp(lz);}
if (rz >= 1) {rs[u] = n + 1; if (rz > 1) ++w; dfsp(rz);}
}
bool dfs(int u) { //修改
if (sz[u] == 2) {
if (rs[u] == 0) return false; //只有左儿子，没法变大
v[u].push_back(1);
return true;
}
int lz = sz[ls[u]], rz = sz[rs[u]], num = 0;
if (rz >= 2 && dfs(rs[u])) return true; //左
if (lz >= 2 && dfs(ls[u])) { //右
for (int i = 1; i < sz[rs[u]]; ++i) v[rs[u]].push_back(0);
return true;
} if (rz) { //左子树+1，右子树-1
v[u].push_back(lz + 1);
if (rz == 1) num = sz[u] - 2; //注意特判一下右子树大小为1的情况
else num = sz[u] - 3;
for (int i = 1; i <= num; ++i) v[u].push_back(0);
return true;
}
return false;
}
void print(int u) {
if (!u || sz[u] == 1) return;
if (v[u].size()) {
for (int i = 0; i < v[u].size(); ++i) cout << v[u][i] << " ";
return;
}
cout << sz[ls[u]] << " ";
print(ls[u]); print(rs[u]);
}
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
while (cin >> a[++tot]){}
--tot; dfsp(a[1]);
if (dfs(1)) {cout << n << " "; print(1);}
else { //n个节点无法满足要求，输出n+1个节点的最小字典序
cout << n + 1 << " ";
for (int i = 1; i <= n; ++i) cout << 0 << " ";
cout << endl;
}
return 0;
}