题解[ARC095D] Permutation Tree
皎月半洒花
2020-02-12 11:24:29
题意：
> 给定一棵树 $\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)$。
```cpp
#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 ;
}
```