题解 CF627F 【Island Puzzle】

> [CF627F Island Puzzle](https://codeforces.com/contest/627/problem/F) ## 题意 - 给定一棵 $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)$，由于复杂度是线性的所以常数什么的就不管了。 ## 代码 ```cpp #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; } ```