题目连接：

看了好长时间才明白了点......

网上讲解很多但感觉都不够详细。。。大概是太弱了吧-_-||

学通了再回来写详解。。。

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #define LL long long  6 using namespace std;  7 const int N=1e5+10;  8 const int inf=1e9+10;  9 int n,k; 10 int rt,ans,sumnode,siz[N],vis[N],d[N]; 11 int dep[N]; //路径长度//dep[0]为子节点个数 12 int f[N]; //重心 13 struct edge 14 { 15     int v,w,nex; 16 }e[N*2]; 17 int head[N]; 18 int cnt; 19 void add(int u,int v,int w) 20 { 21     e[cnt].v=v; 22     e[cnt].w=w; 23     e[cnt].nex=head[u]; 24     head[u]=cnt++; 25 } 26 void getrt(int u,int fa) //找重心 27 { 28     siz[u]=1; 29     f[u]=0; 30     for(int i=head[u];i!=-1;i=e[i].nex) 31     { 32         int v=e[i].v; 33         if(v==fa||vis[v]) continue; 34         getrt(v,u); 35         siz[u]+=siz[v]; 36         f[u]=max(f[u],siz[v]); 37     } 38     f[u]=max(sumnode-siz[u],f[u]); 39     if(f[u]