# CFR 609 E. Minimum spanning tree for each edge ( LCA, Union Find, Kruskal )

Problem - 609E - Codeforces

N, M ≤ 2e5

O( M lg M )

```#include <bits/stdc++.h>
using namespace std;

const int MAXN = int( 2e5 );
const int MAXM = int( 2e5 );

int N, M;
int U[ MAXM ], V[ MAXM ], W[ MAXM ];
int ord[ MAXM ];

int fa[ MAXN ];
int find( int x ) {
return fa[ x ] == x ? x : fa[ x ] = find( fa[ x ] );
}
bool unite( int x, int y ) {
int a = find( x );
int b = find( y );
if( a == b ) return false;
fa[ a ] = b;
return true;
}

set< int > chose;
long long cost;

vector< pair< int, int > > G[ MAXN ];
int dpt[ MAXN ];
int par[ MAXN ][ 20 ];
int maxw[ MAXN ][ 20 ];

void dfs_dpt( int u, int fa, int d ) {
dpt[ u ] = d;
par[ u ][ 0 ] = fa;
for( pair< int, int > p: G[ u ] ) {
int w, v;
tie( w, v ) = p;
if( v == fa ) continue;
maxw[ v ][ 0 ] = w;
dfs_dpt( v, u, d + 1 );
}
}

signed main() {
ios::sync_with_stdio( 0 );
cin >> N >> M;
for( int i = 0; i < M; ++i ) {
cin >> U[ i ] >> V[ i ] >> W[ i ];
--U[ i ], --V[ i ];
ord[ i ] = i;
}
sort( ord, ord + M, [ & ]( int i, int j ) { return W[ i ] < W[ j ]; } );
for( int i = 0; i < N; ++i ) {
fa[ i ] = i;
}
for( int i = 0; chose.size() + 1 != N; ++i ) {
int u, v, w;
tie( u, v, w ) = make_tuple( U[ ord[ i ] ], V[ ord[ i ] ], W[ ord[ i ] ] );
if( unite( u, v ) ) {
G[ u ].emplace_back( w, v );
G[ v ].emplace_back( w, u );
cost += w;
chose.emplace( ord[ i ] );
}
}
memset( par, -1, sizeof( par ) );
dfs_dpt( 0, -1, 0 );
for( int i = 0; i + 1 < 20; ++i ) {
for( int j = 0; j < N; ++j ) {
int m = par[ j ][ i ];
if( m == -1 ) continue;
par[ j ][ i + 1 ] = par[ m ][ i ];
maxw[ j ][ i + 1 ] = max( maxw[ j ][ i ], maxw[ m ][ i ] );
}
}
for( int i = 0; i < M; ++i ) {
if( chose.count( i ) ) {
cout << cost << "\n";
} else {
int u, v, w;
tie( u, v, w ) = make_tuple( U[ i ], V[ i ], W[ i ] );
int best = 0;
if( not ( dpt[ u ] >= dpt[ v ] ) ) {
swap( u, v );
}
for( int i = 20 - 1; dpt[ u ] - dpt[ v ]; --i ) {
if( dpt[ u ] - dpt[ v ] >= 1 << i ) {
best = max( best, maxw[ u ][ i ] );
u = par[ u ][ i ];
}
}
for( int i = 20 - 1; u != v and par[ u ][ 0 ] != par[ v ][ 0 ]; --i ) {
if( par[ u ][ i ] != par[ v ][ i ] ) {
best = max( best, maxw[ u ][ i ] );
best = max( best, maxw[ v ][ i ] );
u = par[ u ][ i ];
v = par[ v ][ i ];
}
}
if( u != v ) {
best = max( best, maxw[ u ][ 0 ] );
best = max( best, maxw[ v ][ 0 ] );
}
cout << cost + w - best << "\n";
}
}
return 0;
}
```