P17553 [JAG 2026 Summer Camp #2] Edge Exchanges

· · 题解

一种 O(n\log n) 的倍增写法。

先钦定一个节点为根。遍历 A 中的每条边，对于它连着的两个节点，令其中深度深的为 v_i，深度浅的为 u_i，即 u_i 是 v_i 的父亲。将在 A 中处于以 v_i 为根的子树中的点，在 B 中染为黑点。

那么题目转化为找在 B 中 u_i 到 v_i 的简单路径中，一条黑白交界的边。

称被染黑的为黑点，未被染黑的为白点。u_i 必定是白的，v_i 必定是黑的。那么此时在 B 中找到点 u_i 和 v_i 的最近公共祖先为 p_i，它要么是白的要么是黑的。若它是黑的，我们截取 u_i 到 p_i 这条链；否则我们截取 v_i 到 p_i 这条链。

显然我们截取出的链一端是白的，一端是黑的，题目问的就是这个黑白交界处。由于原来在树上，我们可以直接倍增求交界处的位置。

最后对于“染黑”这步，在操作中可以不用实际去做。对于每条边的染黑情况，我们都可以 O(1) 判断某个点是否是黑点。记录每个点在 A 中进入和退出的时间戳 bg_i 和 ed_i，若当前节点 x 满足 bg_{v_i} \le bg_x \le ed_x \le ed_{v_i}，则 x 处于 v_i 的子树中，即它是黑点。

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 3;

int n, u1[N], v1[N], u2[N], v2[N], idx[N];
int dep1[N], dep2[N], f[N][23], bg[N], ed[N], tot = 0;
vector<int> ga[N], gb[N];

void dfs2(int u, int fa) {
    dep2[u] = dep2[fa] + 1;
    f[u][0] = fa;
    for (int i = 1; i <= 22; i++) f[u][i] = f[f[u][i - 1]][i - 1];
    for (auto v : gb[u]) {
        if (v == fa) continue;
        dfs2(v, u);
    }
}

void dfs1(int u, int fa) {
    bg[u] = ++tot;
    dep1[u] = dep1[fa] + 1;
    for (auto v : ga[u]) {
        if (v == fa) continue;
        dfs1(v, u);
    }
    ed[u] = ++tot;
}

int LCA(int x, int y) {
    if (dep2[y] > dep2[x]) swap(x, y);
    for (int i = 22; i >= 0; i--) {
        if (dep2[f[x][i]] >= dep2[y])
            x = f[x][i];
    }
    if (x == y) return x;
    int nx, ny;
    for (int i = 22; i >= 0; i--) {
        nx = f[x][i], ny = f[y][i];
        if (nx != ny) x = nx, y = ny;
    }
    return f[x][0];
}

int check(int u, int x) { // u 为黑点
    return (bg[x] <= bg[u] && ed[u] <= ed[x]);
}

int solve(int x, int y, int type, int v) { // type = 0 表示 x 为黑点
    int u;
    for (int i = 22; i >= 0; i--) {
        u = f[x][i];
        if (dep2[u] <= dep2[y]) continue;
        if (check(u, v) ^ type) x = f[x][i];
        else y = f[x][i];
    }
    return idx[x];
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 1; i < n; i++) {
        cin >> u1[i] >> v1[i];
        ga[u1[i]].push_back(v1[i]);
        ga[v1[i]].push_back(u1[i]);
    }
    for (int i = 1; i < n; i++) {
        cin >> u2[i] >> v2[i];
        gb[u2[i]].push_back(v2[i]);
        gb[v2[i]].push_back(u2[i]);
    }
    dfs1(1, 1);
    dfs2(1, 1);
    for (int i = 1; i < n; i++) {
        int u = u2[i], v = v2[i];
        if (dep2[u] > dep2[v]) swap(u, v);
        idx[v] = i;
    }
    for (int i = 1; i < n; i++) {
        int u = u1[i], v = v1[i], lca;
        lca = LCA(u, v);
        if (dep1[u] > dep1[v]) swap(u, v);
        if (check(lca, v)) cout << solve(u, lca, 1, v) << '\n';
        else cout << solve(v, lca, 0, v) << '\n';
    }
    return 0;
}