Problem Description A girl named Gorwin and a boy named Vivin is a couple. They arrived at a country named LOVE. The country consisting of N cities and only N1 edges (just like a tree), every edge has a value means the distance of two cities. They select two cities to live，Gorwin living in a city and Vivin living in another. First date, Gorwin go to visit Vivin, she would write down the longest edge on this path(maxValue).Second date, Vivin go to Gorwin, he would write down the shortest edge on this path(minValue),then calculate the result of maxValue subtracts minValue as the experience of love, and then reselect two cities to live and calculate new experience of love, repeat again and again.
Please help them to calculate the sum of all experience of love after they have selected all cases.
Input There will be about 5 cases in the input file. For each test case the first line is a integer N, Then follows n1 lines, each line contains three integers a, b, and c, indicating there is a edge connects city a and city b with distance c.
[Technical Specification] 1
/*************************************************************************> File Name: bc-30c.cpp> Author: ALex> Mail: zchao1995@gmail.com> Created Time: 2015年02月14日 星期六 21时07分25秒 ************************************************************************/;pi = acos(-1);const int inf = 0x3f3f3f3f;const double eps = 1e-15;LL;typedef pair <int, int> PLL;const int N = 150010;int father[N];LL num[N];struct node{int u, v;LL w;}edge[N];int cmp1 (node a, node b){return a.w < b.w;}int cmp2 (node a, node b){return a.w > b.w;}int find (int x){if (father[x] == -1){return x;}return father[x] = find (father[x]);}int main (){int n;int icase = 1;while (~scanf(“%d”, &n)){for (int i = 1; i <= n – 1; ++i){father[i] = -1;num[i] = 1;scanf(“%d%d%llu”, &edge[i].u, &edge[i].v, &edge[i].w);}father[n] = -1;num[n] = 1;sort (edge + 1, edge + n, cmp1);LL ans = 0;for (int i = 1; i < n; ++i){int u = find (edge[i].u);int v = find (edge[i].v);ans += edge[i].w * num[u] * num[v];num[u] += num[v];father[v] = u;}for (int i = 1; i <= n; ++i){father[i] = -1;num[i] = 1;}sort (edge + 1, edge + n, cmp2);for (int i = 1; i < n; ++i){int u = find (edge[i].u);int v = find (edge[i].v);ans -= edge[i].w * num[u] * num[v];num[u] += num[v];father[v] = u;}printf(“Case #%d: %llu\n”, icase++, ans);}return 0;}
，今天又是美好的一天，我要展示出我优秀的一面。不必一味讨好别人
