Visits: 826

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;
}