题解[ARC095D] Permutation Tree

· · 题解

题意：

给定一棵树 \rm T, 要求构造一个排列 p .

对于每一个 p_i ，找到最大的 j 使得 p_j<p_i，然后在 i,j 间连边。

问是否可以构造出与 \rm T 同构的树。

如果可以，则给出字典序最小的排列。

n\leq 100,000

终于可以从 atcoder 爬题了QAQ

考虑如果给定一个排列，如何通过这种方式生成一棵树。那肯定是按照权值从小到大枚举每个权值所在的位置，每次在 \max\_right 和枚举的 i 之间连边，并更新 \max\_right。

可以发现，由于给定的是排列，局部最大值唯一，那么只会出现「非局部最大值向局部最大值连边」和「上一个版本的局部最大值和当前局部最大值连边」两种连边方式。所以不难看出最后的树的形态就是一个一阶毛毛虫——直径旁边挂着一堆点，每个点与直径的距离均为 1 。所以是否合法求一下直径然后check即可。

考虑如何构造。发现只要求同构，那么肯定是从 1 开始重新编号。对于每个直径上的 x，设与其相连且不在直径上的点的个数为 \deg_x，迄今为止一共有 s 个点已经编完号了，那么只要让 x=s+\deg_x+1，剩下的点依次赋值为 s+1,s+2,s+3\cdots s+\deg_x 就完了。可以知道这样一定是最优的方案。

从直径两端分别处理一下取个字典序最小即可。复杂度 O(n)。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

#define to(k) E[k].to
#define next(k) E[k].next

using namespace std ;

const int N = 200010 ;

struct Edge{
    int to, next ;
}E[N * 2] ;
int n ;
int tot ;
int cnt ;
int q[N] ;
int p[N] ;
int d[N] ;
int fa[N] ;
int vis[N] ;
int dep[N] ;
int deg[N] ;
int head[N] ;

void add(int u, int v){
    to(++ cnt) = v, next(cnt) = head[u], head[u] = cnt ;
    to(++ cnt) = u, next(cnt) = head[v], head[v] = cnt ;
}
int dfs(int u, int faa){
    int ret = u, s ;
    fa[u] = faa, dep[u] = dep[faa] + 1 ;
    for (int k = head[u] ; k ; k = next(k)){
        if (to(k) != faa){
            s = dfs(to(k), u) ;
            if (dep[ret] < dep[s]) ret = s ;
        }
    }
    return ret ;
}
int main(){
    cin >> n ;
    int rt1, rt2, num, u, v ;
    for (int i = 1 ; i < n ; ++ i)
        scanf("%d%d", &u, &v), add(u, v) ;
    rt1 = dfs(1, 0) ; fa[rt1] = 0 ;
    dep[rt1] = 0 ; rt2 = dfs(rt1, 0) ;
    //cout << rt1 << " " << rt2 << endl ;
    for ( ; rt2 ; rt2 = fa[rt2])
        vis[rt2] = 1, d[++ tot] = rt2 ;
    //cout << tot << endl ;
    for (int i = 1 ; i <= n ; ++ i){
        if (vis[i]) continue ; bool ans = 0 ;
        for (int k = head[i] ; k ; k = next(k))
            if (vis[to(k)]) { deg[to(k)] ++, ans = 1 ; break ; }
        if (!ans) return puts("-1"), 0 ;
    }
    num = 0 ;
    for (int i = 1 ; i <= tot ; ++ i){
        for (int j = 1 ; j <= deg[d[i]] ; ++ j)
            p[num + j] = num + j + 1 ;
        p[num + deg[d[i]] + 1] = num + 1 ; num += deg[d[i]] + 1 ;
    }
    num = 0 ;
    for (int i = tot ; i >= 1 ; -- i){
        for (int j = 1 ; j <= deg[d[i]] ; ++ j)
            q[num + j] = num + j + 1 ;
        q[num + deg[d[i]] + 1] = num + 1 ; num += deg[d[i]] + 1 ;
    }
    for (int i = 1 ; i <= n ; ++ i)
        if (p[i] != q[i]){
            if (p[i] < q[i]){
                for (int j = 1 ; j <= n ; ++ j)
                    printf("%d ", p[j]) ; puts("") ;
                return 0 ;
            }
            else {
                for (int j = 1 ; j <= n ; ++ j)
                    printf("%d ", q[j]) ; puts("") ;
                return 0 ;
            }
        }
    for (int j = 1 ; j <= n ; ++ j)
        printf("%d ", p[j]) ; puts("") ;
    return 0 ; 
}