Highway
Accepted : 78		Submit : 275
Time Limit : 4000 MS		Memory Limit : 65536 KB

Highway

In ICPCCamp there were n towns conveniently numbered with 1,2,…,n connected with (n−1) roads. The i -th road connecting towns ai and bi has length ci . It is guaranteed that any two cities reach each other using only roads.

Bobo would like to build (n−1) highways so that any two towns reach each using only highways. Building a highway between towns x and y costs him δ(x,y) cents, where δ(x,y) is the length of the shortest path between towns x and y using roads.

As Bobo is rich, he would like to find the most expensive way to build the (n−1) highways.

Input

The input contains zero or more test cases and is terminated by end-of-file. For each test case:

The first line contains an integer n . The i -th of the following (n−1) lines contains three integers ai , bi and ci .

1≤n≤10⁵
1≤ai,bi≤n
1≤ci≤10⁸
The number of test cases does not exceed 10 .

Output

For each test case, output an integer which denotes the result.

Sample Input

Sample Output

19

15

//题意:有一棵树，问所有点到这棵树中所有点最远距离和为多少

//因为这个是树，所以，从任意一点 dfs 搜最远点，再从最远点 dfs 搜最远点，再dfs一下，这样，保存了2个最远点到任意点的距离，遍历一遍选最大的那个即可，最后减去直径，因为重复算了一次

一共就 4 n 次遍历吧，1800 ms 还行吧

 #include <iostream>

 #include <stdio.h>

 #include <string.h>

 #include <algorithm>

 #include <vector>

 #include <queue>

 using namespace std;

 #define LL long long

 #define INF 0x3f3f3f3f3f3f3f3f

 #define MX 100005

 struct To

 {

     int to;

     LL c;

 };

 int n;

 int far;

 LL step;

 vector<To> road[MX];

 LL dis[][MX];

 void Init()

 {

     for (int i=;i<=n;i++)

         road[i].clear();

 }

 void dfs(int x,int pre,LL s,int kk)//所在位置，从前，距离，第几次

 {

     if (kk!=) dis[kk-][x]=s;

     if (s>step)

     {

         far=x;

         step=s;

     }

     for (int i=;i<(int)road[x].size();i++)

     {

         if (road[x][i].to!=pre)

             dfs(road[x][i].to,x,road[x][i].c+s,kk);

     }

 }

 int main()

 {

     while (~scanf("%d",&n))

     {

         Init();

         for (int i=;i<n-;i++)

         {

             int a,b,c;

             scanf("%d%d%d",&a,&b,&c);

             road[a].push_back((To){b,c});

             road[b].push_back((To){a,c});

         }

         step=;

         dfs(,,,);

         step=;

         dfs(far,,,);

         step=;

         dfs(far,,,);

         LL ans = ;

         for (int i=;i<=n;i++)

             ans += max(dis[][i],dis[][i]);

         ans -= step;

         printf("%I64d\n",ans);

     }

     return ;

 }

巴特西

Highway

Highway

Highway

Input

Output

Sample Input

Sample Output

最新文章

热门文章