AT_agc002_d 题解

题意

有一张 \(n\) 个点，\(m\) 条边的无向图，点的编号从 \(1\) 到 \(n\)，边的编号从 \(1\) 到 \(m\)，第 \(i\) 条边连接定点 \(a_i\) 和 \(b_i\)。保证图联通。

在这张图上，有 \(Q\) 次询问，每次询问中有一对兄弟进行如下操作：

• 最开始的时候哥哥在 \(x_i\) 点，弟弟在 \(y_i\) 点，兄弟两人可以通过边从一个点走到另一个点。

• 兄弟俩需要总计访问恰好 \(z_i\) 个顶点。不过哥哥弟弟都访问的顶点只能算一个。

• 其中兄弟俩经过的边的编号最大值为代价。兄弟俩希望最小化代价。

求每组兄弟的代价。

题解

看到“边的编号最大值”，考虑建出 kruskal 重构树，边权即为编号。

看到“最小化最大值”，考虑二分。设二分到的答案为 \(p\)，则 \(x\) 和 \(y\) 肯定在重构树上一定是尽量向上跳，直到点权超过 \(p\) 为止。此时，\(x\) 和 \(y\) 一定可以去到所有他们的子树的节点，只需要判断两颗子树的大小之和是否 \(\ge z\) 即可。

至于向上跳，可以考虑倍增处理（因为重构树满足从下到上点权单调递增）。复杂度 \(\mathcal{O}(n \log m + q \log^2 n)\)。

代码

int n,m,q,x,y,z,cnt,fa[20][200005],siz[200005],d[200005];
struct edge{int x,y;}e[200005];
int Fa[200005];
int find(int x){return Fa[x]^x?Fa[x]=find(Fa[x]):x;}
void merge(int x,int y,int w){x=find(x),y=find(y);if(x==y)return;d[++cnt]=w,Fa[x]=Fa[y]=fa[0][x]=fa[0][y]=cnt,siz[cnt]=siz[x]+siz[y];
}
void kruskal(){iota(Fa+1,Fa+1+2*n,1),fill(siz+1,siz+1+n,1),cnt=n;fo(i,1,m)merge(e[i].x,e[i].y,i);fd(i,cnt,1)fo(j,1,19)fa[j][i]=fa[j-1][fa[j-1][i]];
}
bool check(int x,int y,int z,int w){fd(i,19,0)if(fa[i][x]&&d[fa[i][x]]<=w)x=fa[i][x];fd(i,19,0)if(fa[i][y]&&d[fa[i][y]]<=w)y=fa[i][y];if(x==y)return siz[x]>=z;return siz[x]+siz[y]>=z;
}
void solve(){cin>>n>>m;fo(i,1,m)cin>>e[i].x>>e[i].y;kruskal(),cin>>q;while(q--){cin>>x>>y>>z;int l=1,r=m,mid,ans;while(l<=r){mid=l+r>>1;if(check(x,y,z,mid))ans=mid,r=mid-1;else l=mid+1;}cout<<ans<<'\n';} 
}