道路修建這道題想來各位不陌生（傳送門在此——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 begin
13 i:=getfat(x);
14 j:=getfat(y);
15 b[i]:=b[i]+b[j];
16 c[j]:=i;
17 end;
18 begin
19 readln(n);
20 fillchar(b,sizeof(b),0);
21 fillchar(c,sizeof(c),0);
22 for i:=1 to n do
23 begin
24 c[i]:=i;
25 b[i]:=1;
26 end;
27 ll:=0;
28 for i:=1 to n-1 do
29 begin
30 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.