[NC记录]AT4114 [ARC095D] Permutation Tree
command_block
2021-05-03 13:04:52
**题意** ： 对于一个排列 $p$ ，按如下规则构造一棵树。
对于每一个 $i$ ，找到最大的 $j$ 使得 $p_j<p_i$，然后在 $i,j$ 间连边。
给出树 $T$ ，若可以构造出与 $T$ 同构的树，则给出字典序最小的排列 $p$ ，否则指出无解。
$n\leq 10^5$ ，时限$\texttt{2s}$。
------------
先考虑给定排列 $p$ 如何生成对应的树。
考虑 $p$ 的逆排列 $p'$。
- 对于每一个 $i$ ，找到最大的 $j$ 使得 $p_j<p_i$，然后在 $i,j$ 间连边。
这条规则变为 ：
- 对于每一个 $p_i'$ ，找到最大的 $p_j'$ 使得 $j<i$，然后在 $p_i',p_j'$ 间连边。
也就是说，$p_i'$ 会向 $\max_{j=1}^{i-1}p_j'$ 连边。
最终产生的树是这样的 ： 每个位置向自己前方的最大值连边，所有前缀最大值形成一条链，其余的点连接在链上，形成一条毛毛虫。
所有毛毛虫都是可以构造出来的。
判定 $T$ 是否为毛毛虫（找直径即可），然后按如下规则构造 ：
设直径两端分别为 $u,v$ ，从两者分别开始一次。
- 结论 ：$(p')^T$ 字典序最大 $\rightarrow p$ 字典序最小。（ $(p')^T$ 指 $p$ 的逆的反转 ）
于是，从末端开始从大到小贪心标号。先编号直径上的点 $v$ ，然后把周围的其他点依次编号，再编号直径上的下一个点。
复杂度 $O(n)$。
```cpp
#include<algorithm>
#include<cstdio>
#include<vector>
#define pb push_back
#define MaxN 100500
using namespace std;
vector<int> g[MaxN];
int rt,f[MaxN],dep[MaxN];
void dfs1(int u,int fa)
{
dep[u]=dep[f[u]=fa]+1;
if (dep[u]>dep[rt])rt=u;
for (int i=0;i<g[u].size();i++)
if (g[u][i]!=fa)
dfs1(g[u][i],u);
}
int n,st[MaxN],tot
,ans1[MaxN],ans2[MaxN],tn;
bool vis[MaxN];
int main()
{
scanf("%d",&n);
for (int i=1,u,v;i<n;i++){
scanf("%d%d",&u,&v);
g[u].pb(v);g[v].pb(u);
}
rt=0;dfs1(1,0);
int ss=rt;rt=0;dfs1(ss,0);
int tmp=2;tot=0;
for (int p=rt;p;p=f[p]){
vis[st[++tot]=p]=1;
tmp+=g[p].size()-2;
}
if (n-tot!=tmp){puts("-1");return 0;}
for (int t=1,tim=n,tn=n;t<=tot;t++){
int u=st[t],savt=tim--;
for (int i=0;i<g[u].size();i++)
if (!vis[g[u][i]])
ans1[tim--]=tn--;
ans1[savt]=tn--;
}
for (int t=tot,tim=n,tn=n;t;t--){
int u=st[t],savt=tim--;
for (int i=0;i<g[u].size();i++)
if (!vis[g[u][i]])
ans2[tim--]=tn--;
ans2[savt]=tn--;
}
bool fl=0;
for (int i=1;i<=n;i++){
if (ans1[i]<ans2[i])break;
if (ans1[i]>ans2[i]){fl=1;break;}
}
for (int i=1;i<=n;i++)
printf("%d ",fl ? ans2[i] : ans1[i]);
return 0;
}
```