终于明白了什么是优秀实现

https://www.luogu.com.cn/article/s6bg6f12

这篇题解的实现是最短的，然而，个人认为这个毫无注释的代码完全看不懂，所以自己写一篇。

首先枚举当前数字。

考虑菊花图怎么做。我们发现将删的边按顺序连一起，发现每次在中心节点上的数字就构成了一个环，用并查集贪心地维护即可。

然后是链。我们发现一个节点最后的数字从哪边来取决于先删左边还是先删右边，对于每个点记一个优先级即可。具体可以画图理解。

受上述启发得到正解：考虑枚举数字

k

, 经过的点依次为

u_1, u_2, \cdots, u_m

, 那么有以下三个要求：

$(u_1, u_2)$ 是 $u_1$ 的所有边中最早删去的边。
$(u_{m - 1}, u_m)$ 是 $u_m$ 的所有边中最迟删去的边。
对于 $i \in [2, m - 1]$ , 在 $u_i$ 的所有边中 $(u_i, u_{i + 1})$ 紧接在 $(u_{i - 1}, u_i)$ 之后删除。

有了这个，仿照菊花图，对每个点开一个并查集，维护优先级，优先级大的是优先级小的祖先，一条边的父亲节点表示对于其和其父亲的公共节点

u

, 在与

u

相邻的所有边中，这两条边的删除顺序是紧挨着的，即其父亲删完后马上删这条。

这里推荐链式前向星存图，方便记边的编号。

注意代码里只开了一个并查集，但是每个点连的边之间是独立的（一条边被拆成了两条有向的）。虚点的意思是，对于一个点连出去的所有边，虚点向最早删除的边连边，最迟删除的边向虚点连边，作用是能让每个点的并查集最后形成一个环，更方便维护信息。

给一个详细的实现。有问题欢迎问我。

CPP

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int N = 6e3 + 10, mod = 998244353;
template<typename T>
void dbg(const T &t) { cout << t << endl; }
template<typename Type, typename... Types>
void dbg(const Type& arg, const Types&... args) {
    cout << arg << ' ';
    dbg(args...);
}
int T, n, res, p[N], fa[N], d[N], sz[N], tot;
int head[N], nxt[N], to[N];
bool in[N], out[N];
void addedge(int u, int v) {
    ++tot;
    nxt[tot] = head[u];
    head[u] = tot;
    to[tot] = v;
}
int find(int u) { return u == fa[u] ? u : fa[u] = find(fa[u]); }
void merge(int x, int y) { // 连边/合并的是共用一个顶点的两条边所代表的点，且 x -> y 表示这个点所有边的删除顺序中 x 后面紧接着 y 
    int u = find(x), v = find(y);
    if (u == v) return ;
    fa[u] = v; sz[v] += sz[u];
    out[x] = in[y] = 1;
}
// 由于虚点的存在，最后肯定会连成一个环。 
bool check(int x, int y, int lim) { // x, y 之间能否连边
    if (in[y] || out[x]) return false; // 已经连过边肯定不合法
    int u = find(x), v = find(y);
    if (u == v && sz[u] != lim) return false; // 如果需要连边的两条边（两个点） 现在所在的链结尾相同且所有点（包括虚点）都已经在了（size 为 d[u] + 1)，就可以连成环了。 
    return true;
}
inline void dfs1(int u, int f) { // 对于每个点 u，它连的边是并查集需要维护的点，u 是虚点，虚点向起点连边，终点向虚点连边 
    if (f != u && check(f, u, d[u] + 1)) res = min(res, u);
    for (int i = head[u]; i; i = nxt[i]) if (i != f) {
    	int v = to[i];
    	if (check(f, i, d[u] + 1)) { // 可以连边就递归下去看看有没有更小的点可以去 
    		dfs1(v, i ^ 1);
		}
	}
}
inline bool dfs2(int u, int f, int tar) { // 以 tar 为目标 
    if (u == tar) {
    	merge(f, u); // 终点向虚点连边
		return true; 
	} 
	for (int i = head[u]; i; i = nxt[i]) if (i != f) {
		int v = to[i];
		if (dfs2(v, i ^ 1, tar)) { // 如果 tar 在 v 的子树内，这条边就需要连 
			merge(f, i);
			return true;
		}
	}
	return false;
}
int main() {
//    freopen("data.in", "r", stdin);
//    freopen("data.out", "w", stdout);
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> T;
    while (T--) {
        cin >> n;
		for (int i = 1; i <= tot; i++) head[i] = in[i] = out[i] = d[i] = 0;
		tot = (n & 1) ? n + 2 : n + 1;
		// 建了 n 个虚点，边的标号从 tot + 1 开始，但是反边是 ^ 1 所以第一条需要是偶数，所以 n 是奇数则 tot <- n + 2 
		for (int i = 1; i <= n; i++) cin >> p[i];
		for (int i = 1, u, v; i < n; i++) {
			cin >> u >> v;
			d[u]++; d[v]++; 
			addedge(u, v); addedge(v, u);
		}
		for (int i = 1; i <= tot; i++) fa[i] = i, sz[i] = 1;
		for (int i = 1; i <= n; i++) {
			int u = p[i];
			res = n + 1;
			dfs1(u, u);
			dfs2(u, u, res);
			cout << res << " \n"[i == n];
		}
    }
    return 0;
}

终于明白了什么是优秀实现

文章操作

相关推荐

评论

终于明白了什么是优秀实现