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

· · 题解

这是一篇乱搞题解。

我们先对 A 树重链剖分，得到 A 树 DFS 序，然后再求出 B 树的 DFS 序。

对于 B 树上的一条边 (u,v)，将其连到 A 树上后，能选择删掉的边，只能从 u 到 v 的路径上的边中选。 对于这些 A 树中合法的边 (x_i,y_i)，我们需要判断它们连接到 B 树上是否合法，我们钦定 u 的深度比 v 大，那么 x_i,y_i 必定是一个在子树 u 内，一个在子树 u 外，这个可以根据 DFS 序直接检查，于是我们就有了一个 O(n^2) 的做法。

考虑优化它，不难想到用并查集维护 DFS 序上下一个还没有确定答案的位置，也就是对于位置 i，如果检查成功，就令 i 的父亲指针指向 i+1。

如果每次都能检查成功的话，复杂度可以做到均摊 O(n\log n)，但事实并非如此，因此我们的复杂度与检查成功的概率有关。

我们考虑玄学优化检查成功的概率，如果 B 树的高度很低，检查成功的概率很低，因为 B 树含有大量大小较小的子树。这里我们把思路反过来，在 B 树上连边，暴力检查 B 树上路径中的每条边，由于高度较低，这个暴力的复杂度是正确的。

然后，我们充分发扬人类智慧，把 B 树上的边 (u_i,v_i) 在 A 树上的路径长度 d_i 从大到小排序，路径长度越长的能检查成功的点数就可能越多，我们希望尽可能增加检查成功的次数，这样可以加速后面的操作。

最后我们发现，如果出题人想要卡我们，就需要弄一堆 d_i 较小的路径，并使能检查成功的边尽可能集中在这些短路径上，这些短路径直接暴力遍历的复杂度是可以接受的，因此我们先优先处理完短路径，然后再从大到小处理完剩下的路径即可。

这么做速度快到飞起，直接跑到了最优解的第一页。

代码如下：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5 + 5 , inf = 0x3f3f3f3f , B = 50;
struct Edge {
    int n , v , id;
}edge[N << 1];
int head[N] , eid;
void eadd(int u , int v , int id) {
    edge[++ eid].n = head[u] , edge[head[u] = eid].v = v , edge[eid].id = id;
}
int dfn[N] , vt , wc[N] , sz[N] , top[N] , fa[N] , dep[N] , id[N] , dfm[N];
vector< pair<int , int> >g[N];
int a[N] , b[N] , va;
struct node {
    int u , v , d , id;
} e[N] , E[N];
bool cmp(node x , node y) {
    if(x.d > B && y.d > B) return x.d > y.d;
    return (x.d <= B) > (y.d <= B);
}
void dfs(int u , int Fa) {
    sz[u] = 1 , dep[u] = dep[Fa] + 1 , fa[u] = Fa;
    for(int i = head[u] ; i ; i = edge[i].n) {
        int v = edge[i].v;
        if(v == Fa) continue;
        id[v] = edge[i].id;
        dfs(v , u);
        sz[u] += sz[v];
        if(sz[wc[u]] < sz[v]) wc[u] = v;
    }
}
void dfs2(int u , int Top) {
    top[u] = Top , dfn[u] = ++ vt , dfm[vt] = id[u];
    if(wc[u]) dfs2(wc[u] , Top);
    for(int i = head[u] ; i ; i = edge[i].n) {
        int v = edge[i].v;
        if(v == wc[u] || v == fa[u]) continue;
        dfs2(v , v);
    }
}
int f[N] , ans[N];
int find(int u) {
    return f[u] == u ? u : f[u] = find(f[u]);
}
void upd(int l , int r , int w , int L , int R) {
    l = find(l);
    while(l <= r) {
        int u = e[dfm[l]].u , v = e[dfm[l]].v;
        if(a[u] > a[v]) swap(u , v);
        if((a[u] < L && L <= a[v] && a[v] <= R) || (L <= a[u] && a[u] <= R && R < a[v])) {
            ans[dfm[l]] = w;
            f[l] = l + 1;  
        }
        l = find(l + 1);
    }
}
void update(int u , int v , int w , int L , int R) {
    while(top[u] != top[v]) {
        if(dep[top[u]] < dep[top[v]]) swap(u , v);
        upd(dfn[top[u]] , dfn[u] , w , L , R);
        u = fa[top[u]];
    }
    if(dep[u] > dep[v]) swap(u , v);
    if(u != v) upd(dfn[u] + 1 , dfn[v] , w , L , R);
}
int dis[N] , F[N] , md , ps[N];
void dfs1(int u , int Fa) {
    a[u] = ++ va , dis[u] = dis[Fa] + 1 , F[u] = Fa;
    md = max(md , dis[u]);
    for(auto v : g[u]) {
        if(v.first == Fa) continue;
        ps[v.first] = v.second;
        dfs1(v.first , u);
    }
    b[u] = va;
}
int LCA(int u , int v) {
    while(top[u] != top[v]) {
        if(dep[top[u]] < dep[top[v]]) swap(u , v);
        u = fa[top[u]];
    }
    return dep[u] < dep[v] ? u : v;
}
int n;
mt19937 rnd(time(NULL));
int main() {
    ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0);
    cin >> n;
    for(int i = 1 ; i < n ; i ++) {
        int u , v;
        cin >> u >> v;
        e[i] = {u , v , 0 , i};
        eadd(u , v , i) , eadd(v , u , i);
    }
    int rt = rnd() % n + 1;
    dfs(rt , 0) , dfs2(rt , rt);
    for(int i = 1 ; i <= n + 1 ; i ++) f[i] = i; 
    for(int i = 1 ; i < n ; i ++) {
        int u , v;
        cin >> u >> v;
        E[i] = {u , v , 0 , i};
        g[u].push_back({v , i}) , g[v].push_back({u , i}); 
    }
    rt = rnd() % n + 1;
    dfs1(rt , 0);
    if(md <= 200) {
        for(int i = 1 ; i < n ; i ++) {
            int u = e[i].u , v = e[i].v;
            if(dep[u] < dep[v]) swap(u , v);
            int L = dfn[u] , R = dfn[u] + sz[u] - 1;
            while(u != v) {
                if(dis[u] < dis[v]) swap(u , v);
                int x = E[ps[u]].u , y = E[ps[u]].v;
                if(dfn[x] > dfn[y]) swap(x , y);
                if((dfn[x] < L && L <= dfn[y] && dfn[y] <= R) || (L <= dfn[x] && dfn[x] <= R && R < dfn[y])) {
                    ans[i] = ps[u];
                    break;
                }
                u = F[u];
            }
        }
    } else { 
        for(int i = 1 ; i < n ; i ++) E[i].d = dep[E[i].u] + dep[E[i].v] - 2 * dep[LCA(E[i].u , E[i].v)];
        sort(E + 1 , E + n , cmp); 
        for(int i = 1 ; i < n ; i ++) {
            int u = E[i].u , v = E[i].v;
            if(a[u] < a[v]) swap(u , v);
            update(u , v , E[i].id , a[u] , b[u]);
        }  
    }
    for(int i = 1 ; i < n ; i ++) cout << ans[i] << '\n';
    return 0;
}