Visits: 323

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;
}