因为每次是找到满足 \(a_u < a_v\) 的最小的二元组 \((a_u, a_v)\) 进行交换,所以这整个过程可以拆分为 \(n\) 个部分,第 \(i\) 个部分是将标签 \(i\) 一路向下转到尽头。
性质 1:整个操作过程是 \(a\) 从这棵树的 DFS 序变为 Exit 序的过程(Exit 序的含义是离开每个结点的时候赋值,可以看下图理解)。且如果 \(1 \sim i\) 这些标签已经被转到了终点(也就是标签 \(i\) 恰好被转完),那么一定是分别被转到了 Exit 序为 \(1, 2, \cdots, i\) 的结点上,而 \(i+1\sim n\) 这些标签则按照剩余子图的 DFS 序依次排列。
白嫖 CF 官方的图片(可以发现,每张 $\text{After pushing } x $ 的图中,绿色的部分都与 \(\text{Exit order of the tree}\) 一图中的部分完全相同,而红色的部分则是从 \(x+1\) 开始对剩余子图按照 DFS 序排列。
由此我们也可以得知,根节点此时的标签为 \(x + 1\),因为它一定是剩余子图的 DFS 序中的首位。
性质 2:每时每刻,一个结点 \(u\) 的所有儿子上的标签的相对大小关系始终保持不变。
不妨设最开始 \(u\) 的所有儿子按照标签依次编号为 \(v_1, v_2, \cdots, v_k\)。考虑每次交换 \((a_u, a_{v_p})\) 的时候,都需要满足 \(a_u < a_{v_p}\)。也就是说明,\(v_p\) 的标签变小了。
- 因为 \(a_u < a_{v_p} < a_{v_{p + 1}} < \cdots < a_{v_k}\),所以 \(v_p\) 的标签依然满足比后面的都小。
- 假设 \(a_u < a_{v_{p - 1}}\),那么相比 \((a_u, a_{v_p})\),存在字典序更小的序列 \((a_u, a_{v_{p - 1}})\),产生矛盾。说明 \(a_{v_1} < \cdots < a_{v_{p - 1}} < a_u < a_{v_{p}}\),所以 \(v_p\) 的标签依然满足比前面的都大。
综上可知,命题是成立的。
有了以上两个结论,就可以开始考虑问题了。因为题目已经给定了某一天的标签数组,根据「性质 2」,我们已经可以把树唯一建出,现在的问题转化利用「性质 1」为判定树的形态是否合法(这也就意味着“多解输出任意解”是唬人的)。
具体来说,我们要判断以下几点:
- 现在正在转的 \(i\) 是否在朝着正确的方向转。(然后为了下面几点的方便,要手动把 \(i\) 转回根 / 转到终点)
- \(1 \sim i - 1\) 是否按照 Exit 序转到了正确的位置。
- \(i + 1 \sim n\) 是否按照剩余子图的 DFS 序排列。
当判定了答案为 YES
之后,考虑计算天数。不难发现,根据上述过程,当标签 \(1 \sim i\) 被转完后,经过的天数就是 \(\sum\limits_{x=1}^{i} \text{dep}(pos_x)\),\(pos_x\) 表示标签 \(x\) 在哪一个结点。
时间复杂度 \(O(n \log n)\)。
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = 3e5 + 5;
vector<int> G[N], G0[N];
long long day;
int cur, n, pv, pt, a[N], fa[N], dep[N];
int prv[N], pst[N], np[N], bp[N], ep[N];
void Build(int u) {
for(int v : G0[u]) {
if(v == fa[u]) continue;
fa[v] = u;
dep[v] = dep[u] + 1;
Build(v);
G[u].pb(v);
}
sort(G[u].begin(), G[u].end(), [](int x, int y){ return a[x] < a[y]; });
}
void Dfs1(int u) {
for(int v : G[u]) Dfs1(v);
pst[u] = ++pt;
ep[pt] = u;
}
bool Find(int u, int v) {
if(u == v) return true;
if(u == 1) return false;
return Find(fa[u], v);
}
void Back(int u) {
if(u == 1) return;
swap(a[u], a[fa[u]]);
day++;
Back(fa[u]);
}
void Dfs2(int u) {
if(a[u] < cur) return;
prv[u] = pv;
bp[pv++] = u;
for(int v : G[u]) Dfs2(v);
}
void Dfs3(int u) {
prv[u] = ++pv;
for(int v : G[u]) Dfs3(v);
}
int main() {
ios::sync_with_stdio(false);
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i];
np[a[i]] = i;
}
for(int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
G0[u].pb(v);
G0[v].pb(u);
}
Build(1);
Dfs1(1);
if(a[1] == 1) {
Dfs3(1);
for(int i = 1; i <= n; i++) {
if(prv[i] != a[i]) {
cout << "NO\n";
return 0;
}
}
cout << "YES\n0\n";
for(int i = 1; i <= n; i++) cout << prv[i] << ' ';
return 0;
}
cur = a[1] - 1;
if(!Find(ep[cur], np[cur])) {
cout << "NO\n";
return 0;
}
Back(np[cur]);
for(int i = 1; i <= n; i++) np[a[i]] = i;
for(int i = 1; i < cur; i++) {
if(np[i] != ep[i]) {
cout << "NO\n";
return 0;
}
}
pv = cur;
Dfs2(1);
for(int i = cur; i <= n; i++) {
if(np[i] != bp[i]) {
cout << "NO\n";
return 0;
}
}
cout << "YES\n";
for(int i = 1; i < cur; i++) day += dep[np[i]];
cout << day << endl;
pv = 0;
Dfs3(1);
for(int i = 1; i <= n; i++) cout << prv[i] << ' ';
return 0;
}