题解：P17553 [JAG 2026 Summer Camp #2] Edge Exchanges
concertb
·
·
题解
UPD：这个超级菜的蒟蒻把复杂度算错了。。。关联工单
DSU 套树剖。
对于 A 中一条边 (u,p)，其中 p 是 u 的父亲，断开变成两个连通块，其中一个是以 u 为根的子树。
在 B 中找到 p 到 u 的路径，则合法的可交换的边 (x,y) 一定满足在这条 p 到 u 的路径上，且 x 在 A 中在以 u 为根的子树（以下简称被标记），y 没有被标记。
从 p 开始向 u 走，遇到的第一个被标记的点的前驱一定没被标记（废话，因为 p 一定不被标记），这一定是合法的边。
于是我们需要维护在 B 上的某一条链中，最小和最大的被标记的点的深度，并支持增加和撤销标记，树剖加线段树即可。
:::info[Code]
```cpp
#include<bits/stdc++.h>
// #define int long long
#define endl '\n'
using namespace std;
const int N=5e5+5;
const int inf=1e9;
int n;
array<vector<pair<int,int> >,N> g,e;
array<int,N> ida,idb,ans;
namespace TrB{
int tot;
array<int,N> fa,dep,sz,son,tp;
array<int,N> in,out,rk;
void dfs1(int u){
sz[u]=1;
for(auto [v,id]:e[u]){
if(v==fa[u]) continue;
fa[v]=u;
idb[v]=id;
dep[v]=dep[u]+1;
dfs1(v);
sz[u]+=sz[v];
if(sz[son[u]]<sz[v])
son[u]=v;
}
return;
}
void dfs2(int u,int top){
in[u]=++tot;
rk[tot]=u;
tp[u]=top;
if(son[u]) dfs2(son[u],top);
for(auto [v,id]:e[u]){
if(v==fa[u]) continue;
if(v==son[u]) continue;
dfs2(v,v);
}
out[u]=tot;
return;
}
int lca(int u,int v){
while(tp[u]!=tp[v]){
if(dep[tp[u]]<dep[tp[v]]) swap(u,v);
u=fa[tp[u]];
}
return dep[u]<dep[v]?u:v;
}
int up(int u,int k){
while(k<=dep[fa[tp[u]]])
u=fa[tp[u]];
return rk[in[u]-(dep[u]-k)];
}
array<int,N<<2> mn,mx;
void push_up(int p){
mn[p]=min(mn[p<<1],mn[p<<1|1]);
mx[p]=max(mx[p<<1],mx[p<<1|1]);
return;
}
void upd(int p,int l,int r,int x,int f){
if(r<x||l>x) return;
if(l==r){
if(f==1) mn[p]=mx[p]=dep[rk[x]];
if(f==-1) mn[p]=inf,mx[p]=-inf;
return;
}
int mid=l+r>>1;
upd(p<<1,l,mid,x,f);
upd(p<<1|1,mid+1,r,x,f);
push_up(p);
return;
}
int qry_mn(int p,int l,int r,int x,int y){
if(r<x||l>y) return inf;
if(x<=l&&r<=y) return mn[p];
int mid=l+r>>1;
return min(qry_mn(p<<1,l,mid,x,y),qry_mn(p<<1|1,mid+1,r,x,y));
}
int qry_mx(int p,int l,int r,int x,int y){
if(r<x||l>y) return -inf;
if(x<=l&&r<=y) return mx[p];
int mid=l+r>>1;
return max(qry_mx(p<<1,l,mid,x,y),qry_mx(p<<1|1,mid+1,r,x,y));
}
int query(int u,int v){
int A=u,B=v,l=lca(u,v);
int res=-inf;
if(v!=l){
v=fa[v];
while(tp[v]!=tp[l]){
res=max(res,qry_mx(1,1,n,in[tp[v]],in[v]));
v=fa[tp[v]];
}
res=max(res,qry_mx(1,1,n,in[l],in[v]));
}
else l=up(u,dep[l]+1);
if(res!=-inf) return up(B,res+1);
res=inf;
while(tp[u]!=tp[l]){
res=min(res,qry_mn(1,1,n,in[tp[u]],in[u]));
u=fa[tp[u]];
}
res=min(res,qry_mn(1,1,n,in[l],in[u]));
assert(res!=inf);
return up(A,res);
}
}
namespace TrA{
int tot;
array<int,N> fa,dep,sz,son;
array<int,N> in,out,rk;
void dfs1(int u){
in[u]=++tot;
rk[tot]=u;
sz[u]=1;
for(auto [v,id]:g[u]){
if(v==fa[u]) continue;
fa[v]=u;
ida[v]=id;
dep[v]=dep[u]+1;
dfs1(v);
sz[u]+=sz[v];
if(sz[son[u]]<sz[v])
son[u]=v;
}
out[u]=tot;
return;
}
void dfs2(int u,int keep){
for(auto [v,id]:g[u]){
if(v==fa[u]) continue;
if(v==son[u]) continue;
dfs2(v,0);
}
if(son[u]) dfs2(son[u],1);
for(auto [v,id]:g[u]){
if(v==fa[u]) continue;
if(v==son[u]) continue;
for(int i=in[v];i<=out[v];i++)
TrB::upd(1,1,n,TrB::in[rk[i]],1);
}
TrB::upd(1,1,n,TrB::in[u],1);
if(u!=1)
ans[ida[u]]=idb[TrB::query(u,fa[u])];
if(!keep){
for(int i=in[u];i<=out[u];i++)
TrB::upd(1,1,n,TrB::in[rk[i]],-1);
}
return;
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
freopen("exchanges6.in","r",stdin);
freopen("out.out","w",stdout);
clock_t Start=clock();
cin>>n;
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
g[u].push_back(make_pair(v,i));
g[v].push_back(make_pair(u,i));
}
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
e[u].push_back(make_pair(v,i));
e[v].push_back(make_pair(u,i));
}
TrB::mn.fill(inf);
TrB::mx.fill(-inf);
TrA::dep[1]=TrB::dep[1]=1;
TrB::dfs1(1);
TrB::dfs2(1,1);
TrA::dfs1(1);
TrA::dfs2(1,0);
for(int i=1;i<n;i++)
cout<<ans[i]<<endl;
cerr<<(double)(clock()-Start)/CLOCKS_PER_SEC<<endl;
return 0;
}
```
:::