题解 P2276 [HNOI2002]农场的果树

首先可以观察出一颗 \(n\) 个节点的二叉树，当其字典序最小的时候，其形态为一条向右偏的链，当其字典序最大的时候，是一条向左偏的链。

由于每一种编码对应唯一的一颗二叉树，我们可以先建树。

然后考虑树上分治，尝试以下三种方式：

1. 变大右子树的字典序

2. 变大左子树的字典序，并将右子树变成一条链

3. 将左子树的大小 \(+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;
}