luoguP4180 [BJWC2010]严格次小生成树

题目大意：

给出一张无向图，求出这个图的严格次小生成树。

解法：

严格次小生成树满足的条件之一是当且仅当只有一条边和最小生成树不同时才有可能是严格次小生成树。

所以我们先求出最小生成树，之后枚举每条不在最小生成树上的边，把这条边加入生成树中，这样子原树就出现了一个环，我们找出这个环中除了当前边最大的边权，这样我们的答案就比最小生成树多了 当前边权减这个环上第二大的边权 这个值的答案，最后对这些所有的答案取最小值就可以了。

其中，对于求环上的第二大的边权，我们可以用树剖做，然后求出每次枚举的边的两个端点在树上的路径上的边权的最大值，然后在用当前边权减去这个最大值就是当前边加入生成树的影响。

（瓶颈）复杂度： \(O(m \log^2 n )\)

Code：

#include <iostream>
#include <algorithm>
using namespace std ;

#define int long long
const int INF = 0x3f3f3f3f3f3f3f3f ;

struct Edge
{
	int u , v , w , id ;
	friend bool operator < ( Edge a , Edge b )
	{
		return a .w < b .w ;
	}
} ed[300005] ;

int n , m , clr[100005] , ans , dt , res = INF , w[100005] , t[800005] , in[800005] ;
int nxt[200005] , to[200005] , head[100005] , len[200005] ;
int dep[100005] , fa[100005] , son[100005] , s[100005] , id[100005] , wt[100005] , top[100005] ;

int find ( int x )
{
	if ( x == clr [ x ] )
		return x ;
	return clr [ x ] = find ( clr [ x ] ) ;
}

int cnt = 0 ;
void insert ( int u , int v , int w )
{
	nxt [ ++ cnt ] = head [ u ] ;
	to [ cnt ] = v ;
	len [ cnt ] = w ;
	head [ u ] = cnt ;
}

void dfs1 ( int x , int la , int d )
{
	dep [ x ] = d ;
	fa [ x ] = la ;
	s [ x ] = 1 ;
	int axx = 0 ;
	for ( int i = head [ x ] ; i ; i = nxt [ i ] )
	{
		int y = to [ i ] ;
		if ( y == la )
			continue ;
		w [ y ] = len [ i ] ;
		dfs1 ( y , x , d + 1 ) ;
		s [ x ] += s [ y ] ;
		if ( s [ y ] > axx )
			son [ x ] = y , axx = s [ y ] ;
	}
}

void dfs2 ( int x , int topf )
{
	top [ x ] = topf ;
	id [ x ] = ++ dt ;
	wt [ dt ] = w [ x ] ;
	if ( ! son [ x ] )
		return ;
	dfs2 ( son [ x ] , topf ) ;
	for ( int i = head [ x ] ; i ; i = nxt [ i ] )
	{
		int y = to [ i ] ;
		if ( y == fa [ x ] || y == son [ x ] )
			continue ;
		dfs2 ( y , y ) ;
	}
}

void pushup ( int k )
{
	if ( t [ k << 1 ] > t [ k << 1 | 1 ] )
	{
		t [ k ] = t [ k << 1 ] ;
		in [ k ] = t [ k << 1 | 1 ] ;
	}
	else if ( t [ k << 1 ] < t [ k << 1 | 1 ] )
	{
		t [ k ] = t [ k << 1 | 1 ] ;
		in [ k ] = t [ k << 1 ] ;
	}
	else
	{
		in [ k ] = max ( in [ k << 1 ] , in [ k << 1 | 1 ] ) ;
	}
}

void build ( int k , int l , int r )
{
	if ( l == r )
	{
		t [ k ] = wt [ l ] ;
		in [ k ] = 0 ;
		return ;
	}
	int mid = ( l + r ) >> 1 ;
	build ( k << 1 , l , mid ) ;
	build ( k << 1 | 1 , mid + 1 , r ) ;
	pushup ( k ) ;
}

int query ( int k , int l , int r , int x , int y , int z )
{
	if ( x <= l && r <= y )
	{
		if ( t [ k ] == z )
			return in [ k ] ;
		return t [ k ] ;
	}
	int mid = ( l + r ) >> 1 , res = 0 ;
	if ( x <= mid )
		res = query ( k << 1 , l , mid , x , y , z ) ;
	if ( y > mid )
		res = max ( res , query ( k << 1 | 1 , mid + 1 , r , x , y , z ) ) ;
	return res ;
}

int find ( int x , int y , int z )
{
	int res = 0 ;
	while ( top [ x ] != top [ y ] )
	{
		if ( dep [ top [ x ] ] < dep [ top [ y ] ] )
			swap ( x , y ) ;
		res = max ( res , query ( 1 , 1 , n , id [ top [ x ] ] , id [ x ] , z ) ) ;
		x = fa [ top [ x ] ] ;
	}
	if ( dep [ x ] > dep [ y ] )
		swap ( x , y ) ;
	if ( x != y )
		res = max ( res , query ( 1 , 1 , n , id [ x ] + 1 , id [ y ] , z ) ) ;
	return res ;
}

signed main ( )
{
	cin >> n >> m ;
	for ( int i = 1 ; i <= n ; ++ i )
		clr [ i ] = i ;
	for ( int i = 1 ; i <= m ; ++ i )
		cin >> ed [ i ] .u >> ed [ i ] .v >> ed [ i ] .w ;
	sort ( ed + 1 , ed + 1 + m ) ;
	for ( int i = 1 ; i <= m ; ++ i )
	{
		int u = ed [ i ] .u , v = ed [ i ] .v , a = find ( u ) , b = find ( v ) ;
		if ( a != b )
		{
			clr [ a ] = b ;
			ed [ i ] .id = 1 ;
			insert ( u , v , ed [ i ] .w ) ;
			insert ( v , u , ed [ i ] .w ) ;
			ans += ed [ i ] .w ;
		}
	}
	dfs1 ( 1 , 0 , 1 ) ;
	dfs2 ( 1 , 1 ) ;
	build ( 1 , 1 , n ) ;
	for ( int i = 1 ; i <= m ; ++ i )
	{
		if ( ed [ i ] .id )
			continue ;
		int u = ed [ i ] .u , v = ed [ i ] .v , w = ed [ i ] .w ;
		int z = find ( u , v , w ) ;
		if ( w != z && w - z < res )
			res = w - z ;
	}
	cout << res + ans << endl ;
	return 0 ;
}

完结撒花！！！