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

Problem - 609E - Codeforces

題意：
給一張圖，分別問每一條邊必須被選擇時的最小生成樹花費是多少。

制約：
N, M ≤ 2e5

解法：
找出原圖的最小生成樹後，做倍增 LCA，同時紀錄向上的瓶頸( 最大 )權值。指定的邊若在原本的生成樹，直接輸出當前最小花費，否則接上去會形成環，要拔掉還上最大權值，令連接的點 ( u, v )，p = lca( u, v )，則關心路徑 ( u, p ) 和 ( v, p ) 中的瓶頸。

時間 / 空間複雜度：
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;
}