题目：

Description

小 C 最近学了很多最小生成树的算法，Prim 算法、Kurskal 算法、消圈算法等等。 正当小 C 洋洋得意之时，小 P 又来泼小 C 冷水了。小 P 说，让小 C 求出一个无向图的次小生成树，而且这个次小生成树还得是严格次小的，也就是说： 如果最小生成树选择的边集是 EM，严格次小生成树选择的边集是 ES，那么需要满足：(value(e) 表示边 e的权值)  这下小 C 蒙了，他找到了你，希望你帮他解决这个问题。

Input

第一行包含两个整数N 和M，表示无向图的点数与边数。 接下来 M行，每行 3个数x y z 表示，点 x 和点y之间有一条边，边的权值为z。

Output

包含一行，仅一个数，表示严格次小生成树的边权和。(数据保证必定存在严格次小生成树)

Sample Input

5 6

1 2 1

1 3 2

2 4 3

3 5 4

3 4 3

4 5 6

Sample Output

11

数据中无向图无自环； 50% 的数据N≤2 000 M≤3 000； 80% 的数据N≤50 000 M≤100 000； 100% 的数据N≤100 000 M≤300 000 ，边权值非负且不超过 10^9 。

题解：

  次小生成树的模板题···

  基本思路是求一次最小生成树··然后枚举那些非树边··找到以非树边两端点在树上路径中最大的一条边··将其删除并换上这条边然后计算目前答案··最后将所有算出的答案取min

  唯一的问题是如何快速求得两端点原树路径上的最大边··可以采用树上倍增的方式··我们预处理出g[i][j],即i向上走2^j条边对应的祖先··以及maxx[i][j]，走2^j的边中的最大值··

  因为这道题是求严格次小的···我们不得不再预处理出一个minx[i][j],为次小值,至于如何求看代码吧··

  然后就是常规的倍增思想··设我们枚举的非树边的两端点为a,b,我们找出它们在树上的lca,然后a和b在跳向lca时求得各自的最大值··注意由于是严格次大的··我们在跳的时候如果此时的maxx已经等于非树边的权值··我们就只能取minx···最后求ab中的最大值就是最大的一条边了

代码：

  

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               using namespace std;const int N=1e5+5;const int M=3e5+5;struct node{ int a,b,val;}ed[M];long long sum=0;int first[N],next[M*2],go[M*2],val[M*2],tot,n,m;int deep[N],maxx[N][20],minx[N][20],g[N][20],father[N];bool vis[M];inline int R(){ char c;int f=0; for(c=getchar();c<'0'||c>'9';c=getchar()); for(;c<='9'&&c>='0';c=getchar()) f=(f<<3)+(f<<1)+c-'0'; return f;}inline bool cmp(node a,node b){ return a.val
               
                maxx[g[j][i-1]][i-1]&&minx[j][i]
                
                 =0;j--) if(deep[a]-(1<
                 
                  =deep[b]) a=g[a][j]; if(a==b) return a; for(i=18;i>=0;i--) if(g[a][i]!=g[b][i]) a=g[a][i],b=g[b][i]; return g[a][0];}inline int find(int a,int b,int lca,int lim){ int i,j,lmax=0,rmax=0; for(i=0;(1<
                  
                   <=deep[a];i++);i--; for(j=i;j>=0;j--) if(deep[a]-(1<
                   
                    =deep[lca]) { if(maxx[a][j]!=lim) lmax=max(lmax,maxx[a][j]); else lmax=max(lmax,minx[a][j]); a=g[a][j]; } for(i=0;(1<
                    
                     <=deep[b];i++);i--; for(j=i;j>=0;j--) if(deep[b]-(1<
                     
                      =deep[lca]) { if(maxx[b][j]!=lim) rmax=max(rmax,maxx[b][j]); else rmax=max(rmax,minx[b][j]); b=g[b][j]; } return max(lmax,rmax);}inline void getans(){ long long ans=2e+18; for(int i=1;i<=m;i++) if(!vis[i]) { int a=ed[i].a,b=ed[i].b,c=ed[i].val; int lca=getlca(a,b); int temp=find(a,b,lca,c); if(temp!=c&&ans>sum-temp+c) ans=sum-temp+c; } cout<
                      
                       <