ABC301Ex 题解
sunkuangzheng
·
·
题解
这怎么放到 Ex 的啊 /fn
【简要题意】
**【题解】**
经典结论是 $u \to v$ 的最小瓶颈路等于最小生成树上 $u,v$ 之间的最大边权。
建最小生成树，考虑第 $i$ 条边的位置，如果它根本不在 $u,v$ 的路径上，或者小于 $u,v$ 路径上的 $\max$，那么对答案肯定没有影响。否则，我们需要找到这条边边权 $+1$ 后新的最小生成树，其实就是断开边 $i$ 后连接两个连通块的最小边权。令边 $i$ 为 $(x,y)$ 且 $dep_x > dep_y$，注意新边 $(x',y')$ 需要满足 $x'$ 在 $x$ 子树内且 $y'$ 不在 $x$ 的子树内，转化为 dfn 序后是**二维数点**模型。由于 $\min$ 没有可减性，我们用树套树维护。
找到新的最小生成树后，只需要求出新的最小生成树上 $u,v$ 之间的最大边，拆成 $(u,x'),(x',y'),(y',v)$ 三段路径在原树上求 $\max$ 即可。
复杂度瓶颈在树套树，时空复杂度均为 $\mathcal O(n \log^2 n)$。
事实上，由于每次二维数点一定有一维形如 $[1,x]$ 或 $[x,n]$，可以正着倒着各做一遍扫描线，线段树维护另一维的 $\min$ 即可做到一只 $\log$。
两只 $\log$ 的实现虽然代码略长（$\text{4.51KB}$），但是基本没有细节，调试较为简单。
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
int top[N],son[N],fa[N],siz[N],dfn[N],dep[N],rt[N*40],tot,ti,tu,tv,u,a,v,q,p[N],mx[N][22],ans[N],f[N][22],val[N],vis[N],n,m,au[N],av[N],aw[N];
int t[N*300],ls[N*300],rs[N*300];
int cmp(int x,int y){return aw[x] < aw[y] ? x : y;}
struct ges{
struct seg{
void upd(int &s,int l,int r,int x,int k){
if(!s) s = ++tot;
if(l == r) return t[s] = cmp(t[s],k),void();
int mid = (l + r) / 2;
if(x <= mid) upd(ls[s],l,mid,x,k); else upd(rs[s],mid+1,r,x,k);
t[s] = cmp(t[ls[s]],t[rs[s]]);
}int qry(int s,int l,int r,int ql,int qr){
if(ql <= l && r <= qr) return t[s];
int mid = (l + r) / 2,ans = 0;
if(ql <= mid) ans = cmp(ans,qry(ls[s],l,mid,ql,qr));
if(qr > mid) ans = cmp(ans,qry(rs[s],mid+1,r,ql,qr));
return ans;
}
}sg;
void upd(int s,int l,int r,int x,int y,int k){
sg.upd(rt[s],1,n,y,k); int mid = (l + r) / 2;
if(l == r) return ;
if(x <= mid) upd(s*2,l,mid,x,y,k); else upd(s*2+1,mid+1,r,x,y,k);
}int qry(int s,int l,int r,int ql,int qr,int tl,int tr){
if(ql > qr || tl > tr) return 0;
if(ql <= l && r <= qr) return sg.qry(rt[s],1,n,tl,tr);
int mid = (l + r) / 2,ans = 0;
if(ql <= mid) ans = cmp(ans,qry(s*2,l,mid,ql,qr,tl,tr));
if(qr > mid) ans = cmp(ans,qry(s*2+1,mid+1,r,ql,qr,tl,tr));
return ans;
}
}seg;
struct dsu{
int fa[N];
int fd(int x){return x == fa[x] ? x : fa[x] = fd(fa[x]);}
void init(){for(int i = 1;i <= n;i ++) fa[i] = i;}
void mg(int x,int y){x = fd(x),y = fd(y),fa[x] = y;}
}d;
vector<pair<int,int>> g[N];
void dfs1(int u,int ft){
fa[u] = ft,dep[u] = dep[ft] + 1,siz[u] = 1,f[u][0] = ft,mx[u][0] = val[u];
for(int i = 1;i <= __lg(dep[u]);i ++) f[u][i] = f[f[u][i-1]][i-1],mx[u][i] = max(mx[u][i-1],mx[f[u][i-1]][i-1]);
for(auto [v,w] : g[u]) if(v != ft) if(val[v] = w,dfs1(v,u),siz[u] += siz[v],siz[v] > siz[son[u]]) son[u] = v;
}void dfs2(int u,int tp){
top[u] = tp,dfn[u] = ++ti; if(son[u]) dfs2(son[u],tp);
for(auto [v,w] : g[u]) if(v != son[u] && v != fa[u]) dfs2(v,v);
}int qrymax(int u,int v){
if(dep[u] < dep[v]) swap(u,v); int ans = 0;
for(int i = __lg(dep[u]);i >= 0;i --) if(dep[f[u][i]] >= dep[v]) ans = max(ans,mx[u][i]),u = f[u][i];
return ans;
}int lca(int u,int v){
while(top[u] != top[v])
if(dep[top[u]] > dep[top[v]]) u = fa[top[u]]; else v = fa[top[v]];
return dep[u] < dep[v] ? u : v;
}bool ck(int u,int v,int x,int y){
int fx = 0,fy = 0;
auto kc = [&](int l,int r,int x){return l <= x && x <= r;};
while(top[u] != top[v]){
if(dep[top[u]] < dep[top[v]]) swap(u,v);
fx |= kc(dfn[top[u]],dfn[u],dfn[x]),fy |= kc(dfn[top[u]],dfn[u],dfn[y]),u = fa[top[u]];
}if(dfn[u] > dfn[v]) swap(u,v);
fx |= kc(dfn[u],dfn[v],dfn[x]),fy |= kc(dfn[u],dfn[v],dfn[y]);
return fx && fy;
}int qpath(int u,int v){int d = lca(u,v); return max(qrymax(u,d),qrymax(v,d));}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin >> n >> m; d.init(); aw[0] = 1e9;
for(int i = 1;i <= m;i ++) cin >> au[i] >> av[i] >> aw[i],p[i] = i;
sort(p + 1,p + m + 1,[&](int x,int y){return aw[x] < aw[y];});
auto add = [&](int x,int y,int w){g[x].emplace_back(y,w),g[y].emplace_back(x,w);};
for(int i = 1;i <= m;i ++)
if(u = d.fd(au[p[i]]),v = d.fd(av[p[i]]),u != v) vis[p[i]] = 1,d.mg(u,v),add(au[p[i]],av[p[i]],aw[p[i]]);
dfs1(1,0),dfs2(1,1);
for(int i = 1;i <= m;i ++) if(!vis[i]) seg.upd(1,1,n,dfn[au[i]],dfn[av[i]],i),seg.upd(1,1,n,dfn[av[i]],dfn[au[i]],i);
for(cin >> q;q --;){
cin >> a >> u >> v,tu = au[a],tv = av[a]; if(dep[tu] < dep[tv]) swap(tu,tv);
if(!ck(u,v,tu,tv)) {cout << "0\n"; continue;}
int d = lca(u,v),mx = max(qrymax(u,d),qrymax(v,d));
if(aw[a] != mx) {cout << "0\n"; continue;}
int k = cmp(seg.qry(1,1,n,dfn[tu],dfn[tu] + siz[tu] - 1,1,dfn[tu] - 1),
seg.qry(1,1,n,dfn[tu],dfn[tu] + siz[tu] - 1,dfn[tu] + siz[tu],n));
if(aw[k] < mx) cout << "0\n";
else if(aw[k] > mx) cout << "1\n";
else{
auto ck = [&](int u,int v){return dfn[u] <= dfn[v] && dfn[v] <= dfn[u] + siz[u] - 1;};
int ru = au[k],rv = av[k];
if(!ck(tu,ru)) swap(ru,rv);
if(min(qpath(u,ru),qpath(v,rv)) <= aw[a]) cout << "0\n"; else cout << "1\n";
}
}
}
```