CF627F Island Puzzle 题解

CF627F Island Puzzle

题意

给定一棵 $n$ 个点的树，每个点上都有一个 $[0,n-1]$ 的数，任意两点上的数都不同。
每次你可以交换 $0$ 所在的点和与其相连的任一点上的数，同时你可以最多加入一条边。
给定目标状态，你需要在加入的边数尽量小的前提下，求出最少的步数，或者判断无法达成目标。
$n \leq 2 \times 10^5$ 。

题解

设初始时 $0$ 在 $s$ ，目标时在 $t$ 。

注意到操作的本质是 $0$ 的移动，同时操作具有可逆性。

因此，我们先不考虑次数最少的要求，先让 $0$ 从 $s$ 以最短距离移动到 $t$ 。

如果此时已经满足目标状态了，说明不需要加入新的边，此时 $0$ 经过的距离即为最少步数。

否则，接下来我们只能加入一条新的边，然后让 $0$ 从 $t$ 出发，走到包含这条新边的环上距离 $t$ 最近的点 $p$ ，绕若干次完整的圈之后，回到 $t$ 。

观察这样操作对权值的变化可以得出， $t$ 到 $p$ 的路径上的所有点的权值都不会改变，同时每绕圈一次，环上除了 $p$ 之外的点上的权值变化形成一个循环，而绕若干圈则为一个轮换。

因此，权值要改变的点加上 $p$ 应该在树上形成一条路径。

由此我们能够确定连边 $(u,v)$ ，可以 $t$ 为根，找到所有权值需要改变的点， $p$ 即为这些点中深度最小的点的父节点，而路径 $(u,v)$ 则由 $p$ 和这些点构成。

如果深度最小的点的父节点不唯一，或者 $p$ 和这些点无法构成一条路径，或者这些点的权值不是目标权值的一个轮换，则说明无解。

最后来考虑最小化操作次数。

对于一条加边 $(u,v)$ ，绕圈的方向有两种 $u\to v$ 和 $v \to u$ ，分别计算取 $\min$ 即可。

假设从 $u \to v$ ，由这个轮换对循环的次数 $c$ 可以得到最小次数为 $2\cdot \operatorname{dist}(t, p) + c \cdot (\operatorname{dist}(u,v) + 1)$ 。

但注意这个最小次数是在先将 $0$ 从 $s$ 移到 $t$ 的前提下，因此如果有重复的路径需要减掉。

总时间复杂度 $\mathcal O(n)$ ，由于复杂度是线性的所以常数什么的就不管了。

代码

#define Fail print(-1), exit(0);
const int N = 2e5 + 7;
int n, a[N], b[N], s, t, p, v[N], d[N];
vi e[N], g, h, A, B;
pi o = mp(N, 0);

bool dfs1(int x, int f) {
	g.pb(x);
	if (x == t) return 1;
	for (auto y : e[x])
		if (y != f && dfs1(y, x)) return 1;
	g.pop_back();
	return 0;
}

void dfs2(int x, int f, int d) {
	if (a[x] != b[x]) {
		h.pb(x), v[x] = 1;
		if (d - 1 == o.fi && f != o.se) Fail;
		if (d - 1 < o.fi) o = mp(d - 1, f);
	}
	for (auto y : e[x])
		if (y != f) dfs2(y, x, d + 1);
}

void dfs3(int x, int f) {
	if (x != p) A.pb(a[x]), B.pb(b[x]);
	for (auto y : e[x])
		if (y != f && v[y]) dfs3(y, x);
}

int dfs4(int x, int f, int d, int t) {
	if (x == t) return d;
	for (auto y : e[x])
		if (y != f) {
			int o = dfs4(y, x, d + 1, t);
			if (o) return o;
		}
	return 0;
}

inline int calc(vi A, vi B) {
	int pos = 0, siz = A.size();
	for (ui i = 0; i < B.size(); i++)
		if (B[i] == A[0]) pos = i;
	if (!pos) return 0;
	for (ui i = 0; i < A.size(); i++)
		if (A[i] != B[(i+pos)%siz]) return 0;
	return pos;
}

inline int S(int x, int y) {
	return dfs4(x, 0, 0, y);
}

inline ll get(int x, int y) {
	int c = calc(A, B);
	return S(s, x) + 1ll * (c - 1) * (A.size() + 1) + 1 + S(y, t);
}

int main() {
	rd(n);
	for (int i = 1; i <= n; i++) rd(a[i]), s = a[i] ? s : i;
	for (int i = 1; i <= n; i++) rd(b[i]), t = b[i] ? t : i;
	for (int i = 1, x, y; i < n; i++)
		rd(x), rd(y), e[x].pb(y), e[y].pb(x);
	dfs1(s, 0);
	for (ui i = 1; i < g.size(); i++) swap(a[g[i-1]], a[g[i]]);
	bool ok = 1;
	for (int i = 1; i <= n; i++) ok &= a[i] == b[i];
	if (ok) return print(0, ' '), print(g.size() - 1), 0;
	dfs2(t, 0, 0), h.pb(p = o.se), v[p] = 1;
	for (auto x : h)
		for (auto y : e[x])
			if (v[y]) ++d[x];
	vi u;
	for (auto x : h)
		if (d[x] == 1) u.pb(x);
		else if (d[x] != 2) Fail;
	if (u.size() != 2u) Fail;
	if (u[0] > u[1]) swap(u[0], u[1]);
	dfs3(u[0], 0);
	if (!calc(A, B)) Fail;
	print(u[0], ' '), print(u[1], ' ');
	ll ans = get(u[0], u[1]);
	reverse(A.begin(), A.end());
	reverse(B.begin(), B.end());
	print(min(ans, get(u[1], u[0])));
	return 0;
}

题意

题解

代码

评论