题目链接：

kruskal重构树。

具体可以参考，或者更推荐的

代码如下：

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define MAXN 100010using namespace std;int n,m,k,cnt,t;int fa[MAXN],head[MAXN],top[MAXN],dep[MAXN],val[MAXN],siz[MAXN],son[MAXN];struct Edge{int u,v,dis;}edge[MAXN<<1];struct Edge2{int nxt,to;}e[MAXN<<1];inline bool cmp(struct Edge x,struct Edge y){return x.dis
         
          maxx) maxx=siz[v],son[now]=v; }}inline void dfs2(int x,int topf){ top[x]=topf; if(son[x]) dfs2(son[x],topf); for(int i=head[x];i;i=e[i].nxt) { int v=e[i].to; if(v==son[x]||v==fa[x]) continue; dfs2(v,v); }}inline int lca(int x,int y){ while(top[x]!=top[y]) { if(dep[top[x]]
         
        
       
      
     
    

BZOJ50题纪念