题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1977
有种很显然的做法：先MST，然后枚举每一条非树边(s,t)，将s,t在MST上对应的路径上找出一条严格小于(s,t)权值且最大的边，然后把(s,t)替换进去，最终可以得到严格次小生成树。明显直接O(n^2)暴力会跪，瓶颈失求树上路径最大边，那么就用树上倍增（Orz CLJ神牛的类Tarjan神做法）来求，这样复杂度就成了O( n log n )，可以AC。
代码：
dcc451da81cb39dbb46a842ad2160924ab183027.jpg.png
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std ;
#define MAXN 100010
#define inf 0x7fffffff
#define MAXM 300010
#define AddEdge( s , t , d )Add( s , t , d ),Add( t , s , d )
#define ll long long
#define MAXD 21
void getint(int&t ){
int ch ;for( ch =getchar( );!( ch >='0'&& ch <='9'); ch =getchar( ));
t = ch -'0';
for( ch =getchar( ); ch >='0'&& ch <='9'; ch =getchar( )) t *=10, t += ch -'0';
}
struct edge{
edge *next ;
int t , d ;
}*head[ MAXN ];
void Add(int s ,int t ,int d ){
edge *p =new( edge );
p -> t = t , p -> d = d , p -> next = head[ s ];
head[ s ]= p ;
}
struct EDGE{
int s , t , d ;
} E[ MAXM ];
bool cmp( EDGE x , EDGE y ){
return x.d < y.d ;
}
struct UNION_SET {
int father[ MAXN ];
UNION_SET( ){
memset( father ,0,sizeof( father ));
}
int Find(int x ){
int i , j = x ;
for( i = x ; father[ i ]; i = father[ i ]);
while( father[ j ]){
int k = father[ j ];
father[ j ]= i ;
j = k ;
}
return i ;
}
void Union(int x ,int y ){
father[Find( x )]=Find( y );
}
} us ;
int n , m ;
ll value =0;
bool used[ MAXN ];
void Kruskal( ){
sort( E +1, E + m +1, cmp );
memset( used ,false,sizeof( used ));
for(int i =0; i ++< m ;)if( us.Find( E[ i ].s )!= us.Find( E[ i ].t )){
value += E[ i ].d ; used[ i ]=true; us.Union( E[ i ].s , E[ i ].t );
AddEdge( E[ i ].s , E[ i ].t , E[ i ].d );
}
}
bool visited[ MAXN ];
int Up[ MAXN ][ MAXD ], h[ MAXN ], N ;
struct Data{
int Max , Smax ;
} dp[ MAXN ][ MAXD ];
Data Make(int _Max ,int _Smax ){
Data u ;
u.Max = _Max , u.Smax = _Smax ;
return u ;
}
Data update( Data x , Data y ){
Data u ;
if( x.Max > y.Max ){
u.Max = x.Max , u.Smax =max( y.Max , x.Smax );
}else if( x.Max < y.Max ){
u.Max = y.Max , u.Smax =max( x.Max , y.Smax );
}else u.Max = x.Max , u.Smax =max( x.Smax , y.Smax );
return u ;
}
void dfs(int v ){
visited[ v ]=true;
for( edge *p = head[ v ]; p ; p = p -> next )if(! visited[ p -> t ]){
Up[ p -> t ][0]= v , h[ p -> t ]= h[ v ]+1, dp[ p -> t ][0]=Make( p -> d ,- inf );
dfs( p -> t );
}
}
void Dp( ){
N =int(log2( n ))+1;
for(int i =0; i ++< N ;)for(int j =0; j ++< n ;){
Up[ j ][ i ]= Up[ Up[ j ][ i -1]][ i -1];
}
for(int i =0; i ++< N ;)for(int j =0; j ++< n ;){
dp[ j ][ i ]=update( dp[ j ][ i -1], dp[ Up[ j ][ i -1]][ i -1]);
}
}
Data Query(int u ,int v ){
if( h[ u ]< h[ v ])swap( u , v );
Data rec =Make(- inf ,- inf );
if( h[ u ]> h[ v ]){
for(int i = N ; i >=0; i --){
if( h[ Up[ u ][ i ]]>= h[ v ]){
rec =update( rec , dp[ u ][ i ]);
u = Up[ u ][ i ];
}
}
}
if( u == v )return rec ;
for(int i = N ; i >=0; i --){
if( Up[ u ][ i ]!= Up[ v ][ i ]){
rec =update( rec ,update( dp[ u ][ i ], dp[ v ][ i ]));
u = Up[ u ][ i ], v = Up[ v ][ i ];
}
}
rec =update( rec ,update( dp[ u ][0], dp[ v ][0]));
return rec ;
}
int main( ){
getint( n ),getint( m );
for(int i =0; i ++< m ;){
getint( E[ i ].s );getint( E[ i ].t );getint( E[ i ].d );
}
Kruskal( );
memset( visited ,false,sizeof( visited ));
Up[1][0]=1, dp[1][0]=Make(- inf ,- inf ), h[1]=0;
dfs(1);
Dp( );
ll ans = inf ; ans *= inf ;
for(int i =0; i ++< m ;)if(! used[ i ]){
ll ret = value ; Data rec =Query( E[ i ].s , E[ i ].t );
if( E[ i ].d > rec.Max ){
ret -= rec.Max ;
ret += E[ i ].d ;
}else{
if( rec.Smax >- inf ){
ret -= rec.Smax ;
ret += E[ i ].d ;
}else continue;
}
ans =min( ans , ret );
}
printf("%lld\n", ans );
return 0;
}
