题解：P13548 [OOI 2022] Air Reform
boruvka 直接做可以做到
代码：
#include <bits/stdc++.h>
#define ll int
using namespace std;
basic_string<ll> vct[400005];
ll val[400005],f[400005];
vector<array<ll,3>> edg;
ll n,m,tot;
inline ll find(ll a){
if (f[a]!=a)f[a]=find(f[a]);
return f[a];
}
ll sz[400005],son[400005],dep[400005],dfn[400005],to[400005],top[400005],ft[400005],T;
void dfs(ll root,ll fa){
ft[root]=fa;
dfn[root]=++T;to[T]=root;
sz[root]=1;son[root]=0;
dep[root]=dep[fa]+1;
for (ll i:vct[root]){
dfs(i,root);
sz[root]+=sz[i];
if (sz[i]>sz[son[root]])son[root]=i;
}
}
void dfs2(ll root,ll fa,ll tp){
top[root]=tp;
if (son[root])dfs2(son[root],root,tp);
for (ll i:vct[root]){
if (i!=son[root]){
dfs2(i,root,i);
}
}
}
inline ll lca(ll u,ll v){
while (top[u]!=top[v]){
if (dep[top[u]]<dep[top[v]])v=ft[top[v]];
else u=ft[top[u]];
}
return (dep[u]<dep[v]?u:v);
}
ll mi[200005];
pair<ll,ll> miid[200005];
/*
1 0
4 3
1 2 1
2 3 2
4 3 3
*/
ll p[200005];
unordered_map<ll,ll> mp[200005];
vector<ll> pp[200005];
inline ll read(){
ll x=0;char c=getchar();
while (!isdigit(c))c=getchar();
while (isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x;
}
ll f2[400005],f3[400005];
vector<array<ll,3>> redo;
ll find2(ll a){
if (f2[a]!=a){
redo.push_back({1,a,f2[a]});
return f2[a]=find2(f2[a]);
}
return a;
}
ll find3(ll a){
if (f3[a]!=a){
redo.push_back({2,a,f3[a]});
return f3[a]=find3(f3[a]);
}
return a;
}
void solve(){
n=read();m=read();
edg.clear();
vector<array<ll,3>> te;
for (ll i=1;i<=n;i++)mp[i].clear();
for (ll i=1;i<=m;i++){
ll u,v,w;
u=read();v=read();w=read();
edg.push_back({w,u,v});
te.push_back({w,u,v});
mp[v][u]=mp[u][v]=1;
}
sort(edg.begin(),edg.end());
for (ll i=1;i<=n;i++)f[i]=i;
for (ll i=1;i<=tot;i++)vct[i].clear();
tot=n;
for (ll i=0;i<edg.size();i++){
ll w=edg[i][0],u=edg[i][1],v=edg[i][2];
ll x=find(u),y=find(v);
if (x==y)continue;
++tot;
f[tot]=tot;
f[x]=tot;
f[y]=tot;
vct[tot].push_back(x);
vct[tot].push_back(y);
val[tot]=w;
}
T=0;
dfs(tot,0);
dfs2(tot,0,tot);
ll c=n;
for (ll i=1;i<=n;i++)f[i]=i;
vector<array<ll,3>> e2;
ll rd=0;
while (c>1){
for (ll i=1;i<=n;i++)pp[i].clear();
for (ll i=1;i<=n;i++){
mi[i]=1e9;
miid[i]={0,0};
pp[find(i)].push_back(i);
}
for (ll i=0;i<=tot+1;i++)f2[i]=f3[i]=i;
for (ll i=1;i<=tot;i++){
if (to[i]<=n)continue;
f2[find2(i)]=find2(i-1);
f3[find3(i)]=find3(i+1);
}
for (ll i=1;i<=n;i++){
if (pp[i].empty())continue;
redo.clear();
for (ll j:pp[i]){
ll x=find2(dfn[j]),y=find2(dfn[j]-1);
redo.push_back({1,x,f2[x]});
f2[x]=y;
x=find3(dfn[j]),y=find3(dfn[j]+1);
redo.push_back({2,x,f3[x]});
f3[x]=y;
}
ll c=i;
ll tt=0;
for (ll j:pp[i]){
ll ps=find3(dfn[j]),ps2=find2(dfn[j]);
ll x=-1,y=-1;
while (ps<=tot){
ll u=to[ps];
if (mp[j].count(u)){
ps=find3(ps+1);
}else{
x=to[ps];
break;
}
}
while (ps2>0){
ll u=to[ps2];
if (mp[j].count(u)){
ps2=find2(ps2-1);
}else{
y=to[ps2];
break;
}
}
// cout<<"?"<< j<<":"<< x<<","<<y<<"\n";
ll mi2=1e9,mi3=0;
if (x!=-1){
ll w=val[lca(x,j)];
if (w<mi2)mi2=w,mi3=x;
}
if (y!=-1){
ll w=val[lca(y,j)];
if (w<mi2)mi2=w,mi3=y;
}
if (mi2<mi[c]){
mi[c]=mi2,miid[c]={j,mi3};
}
//cout<< p[k]<<":"<< mi2<<" "<<mi3<<"\n";
}
reverse(redo.begin(),redo.end());
for (auto j:redo){
if (j[0]==1)f2[j[1]]=j[2];
else f3[j[1]]=j[2];
}
}
for (ll i=1;i<=n;i++){
if (!miid[i].first)continue;
ll u=find(miid[i].first),v=find(miid[i].second);
if (u!=v){
e2.push_back({mi[i],miid[i].first,miid[i].second});
f[u]=v;
c--;
}
}
}
sort(e2.begin(),e2.end());
for (ll i=1;i<=n;i++)f[i]=i;
for (ll i=1;i<=tot;i++)vct[i].clear();
tot=n;
for (ll i=0;i<e2.size();i++){
ll w=e2[i][0],u=e2[i][1],v=e2[i][2];
ll x=find(u),y=find(v);
if (x==y)continue;
++tot;
f[tot]=tot;
f[x]=tot;
f[y]=tot;
vct[tot].push_back(x);
vct[tot].push_back(y);
val[tot]=w;
}
T=0;
dfs(tot,0);
dfs2(tot,0,tot);
for (auto i:te){
cout<< val[lca(i[1],i[2])]<<" ";
}
cout<<"\n";
}
int main(){
cin.tie(0);cout.tie(0);
ios::sync_with_stdio(false);
ll t,g;
t=read();g=read();
while(t--)solve();
return 0;
}