走廊泼水节 （最大生成树）

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int N=50000;
 5 struct ss
 6 {
 7     int u,v,w;
 8     bool operator <(const ss a) const
 9     {
10         return this->w<a.w;
11     }
12 }edg[N];
13 int pre[N],s[N];int n;
14 int f(int x)
15 {
16     if(x==pre[x]) return x;
17     else return x=f(pre[x]);
18 }
19 void init()
20 {
21     for(int i=0;i<n+10;i++)
22     {
23         pre[i]=i,s[i]=1;
24     }
25 }
26 int main()
27 {
28     int t;scanf("%d",&t);
29     while(t--)
30     {
31         ll ans=0;
32         scanf("%d",&n);
33         init();
34         for(int i=0;i<n-1;i++)
35         {
36             scanf("%d%d%d",&edg[i].u,&edg[i].v,&edg[i].w);
37         }
38         sort(edg,edg+n-1);
39         for(int i=0;i<n-1;i++)
40         {
41             //printf("%d %d %d\n",edg[i].u,edg[i].v,edg[i].w);
42             int u=f(edg[i].u);
43             int v=f(edg[i].v);
44             if(u==v) continue;
45             else
46             {
47                 ans+=(long long)(edg[i].w+1)*(s[u]*s[v]-1);
48                 //printf("%lld\n",ans);
49                 pre[v]=u;
50                 s[u]+=s[v];
51             }
52         }
53         printf("%lld\n",ans);
54     }
55  
56     return 0;
57 }