道路修建这道题想来各位不陌生（在此——Bzoj2435），看了此题，一开始以为是最初各个点处于分散状态，然后做了一下，直到发现标程都有点问题，才发现原题是说本来各点已经处于连接完毕的状态（phile：汗。。。 HansBug：论HansBug同学的逗比本性^_^）

既然说道这里了，那么就提出一个新的问题——假如题目别的不变，然后输入的那些边的新的意义如下——首先，一开始各个点处于分散状态，然后按照输入的顺序，每输入一条边就按照当前两边的状态（即两点所在的块的大小之差的绝对值），进行和题目一样的计算，然后将这两个联通，然后进行下一个点——如此循环往复

例如：对于题目中的原有样例：

6

1 2 1

1 3 1

1 4 2

6 3 1

5 2 1

则结果为12（0×1+1×1+2×2+3×1+4×1=12）即边是被一条一条加进来的，不像原题那样本来就是一张完整的树，啊呸，图。。。

 

题解：乍一看题目貌似相当令人头大，但实际上仔细想想不难发现这里面充斥着并查集的影子，并查集可以完美的支持块与块之间的合并操作，则问题来了——怎样同时维护各个块的大小？只要这个解决的，此题也就解决了——其实也不难，由于本题中的合并全都保证不会出现同一块内部的合并（就算出现这个只要在合并前先判断是否必要合并即可），所以每次当你getfat找到最高节点时，同时再进行数量的叠加即可。。。That's all。。。（Hansbug：论HansBug的逗比本性么么哒）

 

1 var 2    i,j,k,l,m,n,a1,a2,a3,a4:longint; 3    ll:int64; 4    b,c:array[0..1000000] of longint; 5 function getfat(x:longint):longint; 6          begin 7               if c[x]<>x then c[x]:=getfat(c[x]); 8               exit(c[x]); 9          end;10 procedure merge(x,y:longint);11           var i,j,k,l:longint;12           begin13                i:=getfat(x);14                j:=getfat(y);15                b[i]:=b[i]+b[j];16                c[j]:=i;17           end;18 begin19      readln(n);20      fillchar(b,sizeof(b),0);21      fillchar(c,sizeof(c),0);22      for i:=1 to n do23          begin24               c[i]:=i;25               b[i]:=1;26          end;27      ll:=0;28      for i:=1 to n-1 do29          begin30               readln(a1,a2,a3);31               j:=getfat(a1);32               k:=getfat(a2);33               ll:=int64(ll+int64(a3*int64(abs(int64(b[j])-int64(b[k])))));  //此处建议不要套那么多int64(),实验表明会严重影响速度，不过此题还是很轻松的34               merge(j,k);35          end;36      writeln(ll);37 end.