Codeforces 1508E Tree Calendar

因为每次是找到满足 \(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 官方的图片(

Codeforces 1508E Tree Calendar

可以发现,每张 $\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」为判定树的形态是否合法(这也就意味着“多解输出任意解”是唬人的)。

具体来说,我们要判断以下几点:

  1. 现在正在转的 \(i\) 是否在朝着正确的方向转。(然后为了下面几点的方便,要手动把 \(i\) 转回根 / 转到终点)
  2. \(1 \sim i - 1\) 是否按照 Exit 序转到了正确的位置。
  3. \(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;
}
上一篇:【小白学Java】D12》》》java中常用API(第二部分)


下一篇:c#获取当前时间 毫秒_new Date()获取当前时间 毫秒