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

· · 题解

想介绍一个用树剖维护的 O(n \log n) 的做法。

首先考虑为什么对于 A 树中的边存在一条 B 树中的边满足限制。我们知道树边断裂后 A 会分成两个连通块，我们考虑对 B 树进行染色，黑色代表这个点在 A 中处于第一个连通块，白色代表这个点在 A 中处于第二个连通块。然后我们再考虑 B 树上新加的边 (u,v)，它一定满足一端是白点一端是黑点。那么 B 树上 u 和 v 对应的路径就不可能是单色的，换句话说一定有不同色结点相邻，那么它们之间的边就是合法边。

用时间戳可以 O(1) 判断一个点的颜色，这里不再赘述。

然后考虑如何找到合法边。对于一组询问 (u,v)，我们在 B 上取 (u,v) 的 \operatorname{lca}，然后取出 (u,v) 与 \operatorname{lca} 颜色不同的点（记为 x），在 \operatorname{lca} 到 x 的链上二分就行了。

然后我们发现直接二分不好处理中点位置，那就考虑维护重链上所有点的信息，两个点不在同一个重链上的时候就考虑较深点的链顶，像这样考虑的链顶不会超过 \log 个，然后在同一个重链内部的二分也是 \log 次，所以时间复杂度是 O(n \log n)。

#include <bits/stdc++.h>
#define mid ((l+r)>>1)
#define pr pair<int,int>
#define fr first
#define sd second
using namespace std;
namespace l_mid_r{
    const int N=5e5+5,K=23;
    int n,tota,totb,cnt,ans[N];
    int dfna[N],dfnb[N],in[N],out[N];
    int fa[N],sz[N],top[N],son[N],id[N];//在哪个重链上
    int pos[N];//在重链的哪个位置
    int st[N][K];
    unordered_map<int,int> mp[N];
    pr e[N];
    vector<int> a[N],b[N],line[N];
    void dfs(int x,int pre){
        dfna[x]=++tota,in[x]=tota;
        for(int i:a[x]){
            if(i==pre) continue;
            dfs(i,x);
        }
        out[x]=tota;
    }
    void dfs1(int x,int pre){
        fa[x]=pre,sz[x]=1;
        for(int i:b[x]){
            if(i==pre) continue;
            dfs1(i,x),sz[x]+=sz[i];
            if(sz[i]>sz[son[x]]) son[x]=i;
        }
    }
    void dfs2(int x,int tp){
        if(tp==x) cnt++,id[x]=cnt;
        id[x]=id[tp],line[id[x]].push_back(x),pos[x]=line[id[x]].size()-1;
        top[x]=tp,dfnb[x]=++totb,st[totb][0]=fa[x];
        if(son[x]) dfs2(son[x],tp);
        for(int i:b[x])
            if(i!=fa[x]&&i!=son[x]) dfs2(i,i);
    }
    int get(int u,int v){return dfnb[u]<dfnb[v]?u:v;}
    int lca(int u,int v){
        if(u==v) return u;
        if((u=dfnb[u])>(v=dfnb[v])) swap(u,v);
        int k=__lg(v-u++);
        return get(st[u][k],st[v-(1<<k)+1][k]);
    }
    bool check(int x,int y,int u){//0在下,1在上
        if(dfna[x]<dfna[y]) swap(x,y);
        return (in[x]<=dfna[u]&&dfna[u]<=out[x]);
    }
    int sol(int u,int v,int x,int y){
        while(top[u]!=top[v]){
            if(fa[top[u]]==v){
                if(check(x,y,top[u])^check(x,y,v)) return mp[top[u]][v];
                else v=top[u];
            }else{
                if(check(x,y,fa[top[u]])^check(x,y,v)) u=fa[top[u]];
                else v=fa[top[u]];
            }
        }
        int k=id[u],l=pos[v],r=pos[u];
        while(l+1<r){
            if(check(x,y,line[k][mid])^check(x,y,line[k][l])) r=mid;
            else l=mid;
        }
        return mp[line[k][l]][line[k][r]];
    }
    int main(){
        scanf("%d",&n);
        for(int i=1,u,v;i<n;i++){
            scanf("%d%d",&u,&v);
            e[i]={u,v};
            a[u].push_back(v);
            a[v].push_back(u);
        }
        for(int i=1,u,v;i<n;i++){
            scanf("%d%d",&u,&v);
            mp[u][v]=mp[v][u]=i;
            b[u].push_back(v);
            b[v].push_back(u);
        }
        dfs(1,0),dfs1(1,0),dfs2(1,1);
        for(int i=1;i<K;i++)
            for(int j=1;j+(1<<i)-1<=n;j++)
                st[j][i]=get(st[j][i-1],st[j+(1<<(i-1))][i-1]);
        for(int i=1;i<n;i++){
            int u=lca(e[i].fr,e[i].sd);
            if(check(e[i].fr,e[i].sd,u)^check(e[i].fr,e[i].sd,e[i].fr)) 
                ans[i]=sol(e[i].fr,u,e[i].fr,e[i].sd);
            else ans[i]=sol(e[i].sd,u,e[i].fr,e[i].sd);
        }
        for(int i=1;i<n;i++) printf("%d\n",ans[i]);
        return 0;
    }
}
signed main(){return l_mid_r::main();}