题解：P17553 [JAG 2026 Summer Camp #2] Edge Exchanges

qixiandaa · 2026-10-19 16:49:01 · 题解

观察这个题意并且手玩样例之后可以发现如果删去树 A 里连接 u 和 v 的边，那么新加进来的边一定要连接 v的子树和除此之外的部分。

那么在 B 里新加的这条连接 u 和 v 的边会成环，为了保持树的形态，要删去的必须是 B 树里 u 和 v 路径上的部分，同时要满足上面那个条件。

我们把 v 子树里的点都染成一种颜色，只需要找 u 到 v 路径上第一个颜色不同的点对就可以。这个显然可以拆成 u 到 lca 和 lca 到 v 两条路径做。

然后直接倍增找最近的与 u 不同颜色的点即可。v 同理。判断一个点是什么颜色可以按照它在 A 树里的 dfn 序是否在某个区间内 O(1) 判断，这样倍增就是 O(n log n) 的。

没有无解的情况。

然后写一个很神秘的 O(n \log ^3 n) 做法（赛时做法）。

找颜色不同的点可以转化为找路径上第一个 1，直接倍增路径然后树剖查询最大值是否为 1，依此上跳即可。

剩下的是如何 O(1) 染色，我们进入每个子树时维护一个递减的时间戳，然后出来时计算这个子树的父边的答案，没遍历过的子树设为无穷大。这样子树里所有点的时间戳都小于子树根，这样就可以以与当前子树根的大小关系来作为 01 的划分依据，倍增时找第一个大于根的即可。因为不会重复遍历一个子树所以这个是对的。

使用线段树二分应该可以优化到 O(n \log ^2 n)，但很显然都不如倍增，拉完了。

给出 O(n \log ^3 n) 代码。

#include <bits/stdc++.h>
#define loop(i, a, b) for(int i = (a) ; i <= (int)(b) ; i++)
#define rloop(i, a, b) for(int i = (a) ; i >= (int)(b) ; i--)
#define lowbit(x) ((x) & (-(x)))
#define ls (k << 1)
#define rs (k << 1 | 1)
#define mid ((l + r) >> 1)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N = 5e5 + 5;
const int INF = 5e6;
int n, m, k, tot, cnt;
int a[N], ans[N], val[N], up[N][21];
int son[N], dfn[N], top[N], dep[N], siz[N];
struct node {
    int v, id;
} fa[N];
vector<node> A[N], B[N];

struct data {
    ll mx, mn;   
};

data empty_data = {-INF, INF};

inline data operator + (const data &x, const data &y) {
    return {max(x.mx, y.mx), min(x.mn, y.mn)};
}

data tr[N << 2];

void push_up(int k) {
    tr[k] = tr[ls] + tr[rs];
}

void update_point(int l, int r, int k, int p, int v) {// p is dfn
    if(l == r) {
        tr[k] = {v, v};
        return;
    }
    if(p <= mid) update_point(l, mid, ls, p, v);
    else update_point(mid + 1, r, rs, p, v);
    push_up(k);
}

data query(int l, int r, int k, int ql, int qr) {
    if(ql <= l && r <= qr) return tr[k];
    data res = empty_data;
    if(ql <= mid) res = res + query(l, mid, ls, ql, qr);
    if(qr > mid) res = res + query(mid + 1, r, rs, ql, qr);
    return res;
}

data query_path(int x, int y) {
    data res = empty_data;
    while(top[x] != top[y]) {
        if(dep[top[x]] < dep[top[y]]) swap(x, y);
        res = (res + query(1, n, 1, dfn[top[x]], dfn[x]));
        x = fa[top[x]].v;
    }
    if(dep[x] > dep[y]) swap(x, y);
    res = (res + query(1, n, 1, dfn[x], dfn[y]));
    return res;
}

int lca(int x, int y) {
    while(top[x] != top[y]) {
        if(dep[top[x]] < dep[top[y]]) swap(x, y);
        x = fa[top[x]].v;
    }
    if(dep[x] > dep[y]) swap(x, y);
    return x;
}

void dfsB1(int u, int f) {
    dep[u] = dep[f] + 1, siz[u] = 1; 
    up[u][0] = f;
    loop(i, 1, 20) up[u][i] = up[up[u][i - 1]][i - 1];
    for(auto e : B[u]) {
        int v = e.v;
        if(v == f) continue;
        fa[v] = {u, e.id};
        dfsB1(v, u);
        siz[u] += siz[v];
        if(siz[v] > siz[son[u]]) son[u] = v;
    }
}

void dfsB2(int u, int topf) {
    dfn[u] = ++tot;
    update_point(1, n, 1, tot, n + 8); 
    top[u] = topf;
    if(!son[u]) return ;
    dfsB2(son[u], topf);
    for(auto e : B[u]) {
        int v = e.v;
        if(v == fa[u].v || v == son[u]) continue;
        dfsB2(v, v);
    }
}

void dfsA(int u, int f) {
    cnt--;
    update_point(1, n, 1, dfn[u], cnt);
    val[u] = cnt;       
    for(auto e : A[u]) {
        int v = e.v;
        if(v == f) continue;
        dfsA(v, u);
        int s = v, t = u;
        int lc = lca(s, t);
        rloop(i, 20, 0) {
            if(up[s][i] && dep[up[s][i]] >= dep[lc] && query_path(v, up[s][i]).mx <= val[v]) s = up[s][i];
        }
        rloop(i, 20, 0) {
            if(up[t][i] && dep[up[t][i]] >= dep[lc] && query_path(u, up[t][i]).mn > val[v]) t = up[t][i];   
        }
        if(s != lc) ans[e.id] = fa[s].id;
        else if(t != lc) ans[e.id] = fa[t].id;
        else {
            ans[e.id] = -1; 
            //loop(i, 1, n) cout << val[i] << "\n";
            //cout << query_path(3, 1).mx << "\n";      
        }
    }
}

void solve() {
    cin >> n;
    loop(i, 1, n - 1) {
        int u, v; cin >> u >> v;
        A[u].push_back({v, i}), A[v].push_back({u, i});
    }
    loop(i, 1, n - 1) {
        int u, v; cin >> u >> v;
        B[u].push_back({v, i}), B[v].push_back({u, i});
    }
    dfsB1(1, 0);
    dfsB2(1, 1);
    cnt = n + 5;
    dfsA(1, 0);
    loop(i, 1, n - 1) cout << ans[i] << "\n";
}

signed main() {
    //freopen("trees.in", "r", stdin);
    //freopen("trees.out", "w", stdout);
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    // int t; cin >> t; while(t--)
    solve();
    return 0;
}