就是 \(m\) 组询问补图的最小生成树上的树链最大值。有两种基本思路求这棵树。
第一种，Kruskal，基于找到最小的边使两端点不连通。考虑补图中 \((x,y)\) 的边权，它是原图最小生成树上的树链最大值。从小到大枚举补图的边，相当于从小到大枚举原图最小生成树的边 \((u,v,w)\)，然后：
令原图上，连接这条边之前，\(u\) 所在连通块为 \(S\)，\(v\) 所在连通块为 \(T\)，那么对于 \(x\in S,y\in T\)，必然有补图中 \((x,y)\) 的边权恰为 \(w\)。当然这建立在补图中 \((x,y)\) 这条边存在的前提下。
所以直接模拟这个过程，暴力枚举 \(x\) 所在补图连通块 \(X\)（显然 \(X\subseteq S\)），然后不断地去寻找 \(y\) 所在补图连通块 \(Y(Y\subseteq T)\)。为了判断 \(X\) 与 \(Y\) 是否可以合并，枚举 \(x\in X\) 和 \(y\in T\)，观察 \((x,y)\) 这条边在原图是否不存在即可。
四重循环。这个复杂度分三部分。其一，合并 \(X\) 与 \(Y\)。启发式合并即可总计 \(\mathcal O(n\log n)\)。
其二，寻找 \(Y\) 的过程中枚举 \(y\)。注意到每对 \((x,y)\) 至多枚举一次，\(y\) 会被跳过当且仅当原图存在边 \((x,y)\)。所以总共 \(\mathcal O(m)\)。
其三，合并 \(X\) 与 \(Y\) 的次数。显然是 \(\mathcal O(n)\)。
然后注意到判断 \((x,y)\) 原图是否有边是 \(\Theta(\log m)\) 的。于是令 \(m=\Omega(n)\) 则总复杂度 \(\mathcal O(m\log m)\)。这个应该是 CF 的 std。
第二种，Boruvka，基于对每个点找到离开所在连通块的最小边。对原图建出 Kruskal 重构树，补图中 \((x,y)\) 边权为 \(w_{\operatorname {lca(x,y)}}\)。
问题转化为，对于所有叶子结点 \(u\)，找到其最深的祖先 \(a\)，满足 \(a\) 的子树内存在一个 \(v\) 使得：
-
\(v\) 不在 \(u\) 的连通块内；
-
原图中 \((u,v)\) 无边。
考虑连通块在重构树上形如一段 dfn 区间。合并连通块就是合并区间，同时子树也是一段 dfn 区间，于是二分一下即可找到 \(a\)。
对于原图无边这个限制，枚举 \(u\) 的所有 \(k\) 个出点，然后把查询区间暴力分成 \(\mathcal O(k)\) 个子段。这样一次 Boruvka 的过程只会查 \(\mathcal O(m)\) 个区间。
总复杂度 \(\mathcal O(n\log^2 n)\)。
个人写的是第一种思路。有点难调。
#include <cstdio>
#include <vector>
#include <algorithm>
#include <set>
#include <cstring>
using namespace std;
namespace fIO{
char c;void re(int &x){
x=0;c=getchar();
while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
}
char st[20];int tp;
void wr(int n){
while(n) st[++tp]=n%10+48,n/=10;
while(tp) putchar(st[tp--]);
}
}using fIO::re;using fIO::wr;
const int N=231231;
struct U{
int anc[N];
void set(int n){for(int i=1;i<=n;++i) anc[i]=i;}
int qry(int x){return anc[x]==x?x:anc[x]=qry(anc[x]);}
bool sam(int x,int y){return qry(x)==qry(y);}
void mrg(int x,int y){anc[qry(x)]=qry(y);}
}O,B;
namespace AT{
struct edg{int v,w;};
vector<edg> vc[N];
void lnk(int x,int y,int w){
vc[x].push_back((edg){y,w});vc[y].push_back((edg){x,w});
}
int f[N][18],anc[N][18],dep[N];
void build(int now,int lst){
anc[now][0]=lst;dep[now]=dep[lst]+1;
for(int i=1;(1<<i)<dep[now];++i) anc[now][i]=anc[anc[now][i-1]][i-1],
f[now][i]=max(f[now][i-1],f[anc[now][i-1]][i-1]);
for(auto[v,w]:vc[now]) if(v!=lst) f[v][0]=w,build(v,now);
}
int qry(int x,int y){
int res=0;if(dep[x]<dep[y]) swap(x,y);
for(int i=17;~i;--i) if((1<<i)<=dep[x]-dep[y])
res=max(res,f[x][i]),x=anc[x][i];
for(int i=17;~i;--i) if(anc[x][i]!=anc[y][i])
res=max(res,max(f[x][i],f[y][i])),x=anc[x][i],y=anc[y][i];
if(x!=y) res=max(res,max(f[x][0],f[y][0]));
return res;
}
void clr(int n){
for(int i=1;i<=n;++i) vc[i].clear(),memset(anc[i],0,sizeof(anc[i]));
}
}
set<int> blk[N],sub[N];
int merg(int X,int Y){
if(blk[X].size()>blk[Y].size()) swap(X,Y);
for(int x:blk[X]) blk[Y].insert(x);
return Y;
}
vector<int> vc[N],del;int pos[N];
void mrgsub(int &u,int &v,int w){
if(sub[B.qry(u)].size()>sub[B.qry(v)].size()) swap(u,v);
int pu=u,pv=v;u=B.qry(u);v=B.qry(v);
for(int X:sub[u]){
del.clear();int p=X;
for(int Y:sub[v]){
for(int x:blk[X]){
bool flg=0;for(int y:blk[Y]){
auto it=lower_bound(vc[x].begin(),vc[x].end(),y);
if(it==vc[x].end()||*it!=y){
flg=1;p=merg(p,Y);del.push_back(Y);AT::lnk(x,y,w);break;
}}
if(flg) break;
}
}
for(int Y:del) sub[v].erase(Y);
sub[v].insert(p);
}
B.mrg(u,v);u=pu;v=pv;
}
struct edg{int x,y,w,id;}e[N];
int ans[N];
int main()
{
int T;re(T);while(T--){
int n,m;re(n);re(m);O.set(n);B.set(n);AT::clr(n);
for(int i=1;i<=n;++i) pos[i]=i,vc[i].clear(),
sub[i].clear(),sub[i].insert(i),blk[i].clear(),blk[i].insert(i);
for(int i=1;i<=m;++i) re(e[i].x),re(e[i].y),re(e[i].w),e[i].id=i,
vc[e[i].x].push_back(e[i].y),vc[e[i].y].push_back(e[i].x);
for(int i=1;i<=n;++i) sort(vc[i].begin(),vc[i].end());
sort(e+1,e+m+1,[](edg u,edg v){return u.w<v.w;});
for(int i=1;i<=m;++i) if(!O.sam(e[i].x,e[i].y))
mrgsub(e[i].x,e[i].y,e[i].w),O.mrg(e[i].x,e[i].y);
AT::build(1,0);
for(int i=1;i<=m;++i) ans[e[i].id]=AT::qry(e[i].x,e[i].y);
for(int i=1;i<=m;++i) wr(ans[i]),putchar(' ');puts("");
}
}