ARC095F Permutation Tree 题解

ARC095F Permutation Tree

题意

• 对于一个 $1\sim n$ 的排列 $p_{1\cdots n}$，可以通过如下方法生成一棵树：
  • 对于 $i$，如果 $p_i \ne 1$，则找到一个最大的 $j$ 满足 $p_j < p_i$，在 $i,j$ 之间连边。
• 现在要求找到一个字典序最小的生成的树与给定的树同构的排列，或判断无解。
• $n \le 10^5$。

题解

给定树必须要是一个毛毛虫，即去掉叶子之后要是一条链。

正反方向贪心一下，取字典序更小的方案即可。

代码

const int N = 1e5 + 7;
int n, d[N], c[N], l, r;
vi e[N];
bool v[N];

inline int find(int x) {
	for (int y : e[x])
		if (!v[y] && d[y] != 1) return y;
	return 0;
}

inline vi work(int l, int r) {
	vi ret(1, 1), p(1, d[l] - 2);
	for (int i = 1; i <= n; i++) v[i] = 0;
	while (l != r) v[l] = 1, l = find(l), p.pb(d[l] - 2);
	int t = 1;
	for (int x : p) {
		dbg(x);
		for (int i = 1; i <= x; i++) ret.pb(t + i + 1);
		ret.pb(t + 1), t += x + 1;
	}
	ret.pb(n);
	return ret;
}

int main() {
	rd(n);
	if (n == 2) return prints("1 2"), 0;
	for (int i = 1, x, y; i < n; i++)
		rd(x, y), e[x].pb(y), e[y].pb(x), ++d[x], ++d[y];
	for (int i = 1; i <= n; i++) c[i] = d[i];
	for (int i = 1; i <= n; i++)
		if (d[i] == 1) --c[e[i][0]], --c[i];
	if (*max_element(c + 1, c + n + 1) > 2) return print(-1), 0;
	if (!*max_element(c + 1, c + n + 1)) {
		print(1, ' ');
		for (int i = 3; i < n; i++) print(i, ' ');
		print(2, ' '), print(n);
		return 0;
	}
	for (int i = 1; i <= n; i++)
		if (c[i] == 1) r = i;
	for (int i = n; i; i--)
		if (c[i] == 1) l = i;
	vi ans = min(work(l, r), work(r, l));
	for (int x : ans) print(x, ' ');
	return 0;
}