题目大意：

给你一棵n个结点树，然后根据这棵树构造一个完全图，求完全图的一条最长的哈密顿路径。

构造方式是，完全图中的dis(u, v)就等于树上的u和v的距离。

 

题解：

这。。。这。。不就是杜教的那个题

还是弱化版的orz

需要注意的是，不是完全一样，这个题求的是哈密顿回路，需要删除一个最小的路径

答案就很简单了，找到重心以后。

如果有一棵子树大小为(n+1)/2，那么就只能删除连向那个子树的边

如果没有，那么就遍历一遍所有连向重心的边，选一个最小的删除即可。

杜教题连接 http://www.cnblogs.com/Saurus/p/7077966.html

 

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #define fi first#define se secondusing namespace std;const int maxn = 1e5 + 100;typedef long long LL;typedef pair
          
            PLI;typedef pair
           
             PII;vector
            
              G[maxn];set
             
               S;int son[maxn], sz[maxn];int tree[maxn*4];int n, tot;LL ANS = 0, Min = 1e18;void dfs0(int x, int fa){ sz[x] = 1; for(auto e : G[x]){ if(e.fi == fa) continue; dfs0(e.fi, x); sz[x] += sz[e.fi]; son[x] = max(son[x], sz[e.fi]); } son[x] = max(son[x], n - sz[x]);}void dfs(int x, int fa, LL v){ sz[x] = 1; for(auto e : G[x]){ if(e.fi == fa) continue; dfs(e.fi, x, e.se+v); sz[x] += sz[e.fi]; } ANS += v;}int main(){ cin>>n; for(int i = 1; i < n; i++){ int x, y, w; cin>>x>>y>>w; G[x].push_back({y, w}); G[y].push_back({x, w}); } int X; dfs0(1, 1); for(int i = 1; i <= n; i++) if(son[i] <= n/2) X = i; dfs(X, X, 0); for(auto e : G[X]){ if(sz[e.fi] == (n+1)/2) { Min = e.se; break; } Min = min(e.se, Min); } cout<