51nod 配对（求树的重心）-白红宇

51nod 配对（求树的重心）

阅读量：5265 次

发布时间：2019-06-14

本文共 2042 字，大约阅读时间需要 6 分钟。

传送门：

给出一棵n个点的树，将这n个点两两配对，求所有可行的方案中配对两点间的距离的总和最大为多少。

Input

一个数n（1<=n<=100,000,n保证为偶数）接下来n-1行每行三个数x,y,z表示有一条长度为z的边连接x和y（0<=z<=1,000,000,000）

Output

一个数表示答案

Input示例

61 2 11 3 11 4 13 5 14 6 1

Output示例

7//配对方案为（1，2）（3，4）（5，6）

这题一开始完全没思路，后来在评论中看到有人说是求树的重心再到其他点的距离和，就去查了下树的重心的定义——找到一个点,其所有的子树中最大的子树节点数最少,那么这个点就是这棵树的重心。对于这题，配对的两点的路径一定要经过重心，这样才能保证距离最大，而如果任意两点都经过重心，他们的总距离一定是重心到其他点的距离和。这个模拟一下就能知道了。通过这题顺带学习一下树的重心。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #include 
               
                #include 
                
                 #define X first#define Y second#define clr(u,v); memset(u,v,sizeof(u));#define in() freopen("data","r",stdin);#define out() freopen("ans","w",stdout);#define Clear(Q); while (!Q.empty()) Q.pop();#define pb push_backusing namespace std;typedef long long ll;typedef pair
                 
                   pii;const int maxn = 1e5 + 10;const int INF = 0x3f3f3f3f;struct Edge{ int v, to; ll w;} E[2*maxn];int head[maxn], cnt, n, sz, pos;int vis[maxn], sum[maxn];ll dis[maxn];ll ans = 0;void init(){ sz = INF; clr(head, -1); clr(sum, 0); clr(dis, 0); cnt = 0; ans = 0;}void addedge(int v, int u, ll w){ E[cnt].v = u, E[cnt].w = w, E[cnt].to = head[v]; head[v] = cnt++;}void dfs(int cur)//求树的重心{ vis[cur] = 1; int temp = 0; for (int i = head[cur]; ~i; i = E[i].to) { int v = E[i].v; if (vis[v]) continue; dfs(v); temp = max(temp, sum[v] + 1);//求最大子树节点数 sum[cur] += sum[v] + 1; } temp = max(temp, n - sum[cur] - 1);//无向树还要考虑上半部分 if (temp < sz) { sz = temp; pos = cur; }}void solve(int cur)//算距离{ vis[cur] = 1; for (int i = head[cur]; ~i; i = E[i].to) { int v = E[i].v; if (vis[v]) continue; dis[v] = dis[cur] + E[i].w; ans += dis[v]; solve(v); }}int main(){ init(); int v, u; ll w; scanf("%d", &n); for (int i = 1; i < n; i++) { scanf("%d%d%I64d", &v, &u, &w); addedge(v, u, w), addedge(u, v, w); } dfs(1); clr(vis, 0); //cout << sz << " " << pos << endl; solve(pos); cout << ans << endl; return 0;}

转载于:https://www.cnblogs.com/scaugsh/p/6349836.html

你可能感兴趣的文章