2435: [Noi2011]道路修建
Time Limit: 10 Sec Memory Limit: 128 MB Submit: 2188 Solved: 639 [ ][ ]
Description
在 W 星球上有 n 个国家。为了各自国家的经济发展，他们决定在各个国家
之间建设双向道路使得国家之间连通。但是每个国家的国王都很吝啬，他们只愿意修建恰好 n – 1条双向道路。 每条道路的修建都要付出一定的费用， 这个费用等于道路长度乘以道路两端的国家个数之差的绝对值。例如，在下图中，虚线所示道路两端分别有 2 个、4个国家，如果该道路长度为 1，则费用为1×|2 – 4|=2。图中圆圈里的数字表示国家的编号。
Input
输入的第一行包含一个整数n，表示 W 星球上的国家的数量，国家从 1到n编号。接下来 n – 1行描述道路建设情况，其中第 i 行包含三个整数ai、bi和ci，表示第i 条双向道路修建在 ai与bi两个国家之间，长度为ci。
Output
输出一个整数，表示修建所有道路所需要的总费用。
Sample Input
6
1 2 1
1 3 1
1 4 2
6 3 1
5 2 1
Sample Output
20
HINT
n = 1,000,000 1≤ai, bi≤n 0 ≤ci≤ 10^6
Source
题解：其实就是个搜索，由于题目中给了一棵树，所以直接建树，然后求出每个点有多少子孙（算自己）。。。本身应该不难的，但是对于P党问题来了——BFS嘛，搞死了还是超时（坑爹的int64运算简直慢到哭）；DFS呵呵直接爆栈不解释（对于C++党的linux下系统栈无限表示严重鄙视！！TT ），于是我还是壮烈的TLE了，求神犇帮助（不过程序算法应该没有问题，就是int64害得......）
BFS：
1 type 2 point=^node; 3 node= record 4 g,w:longint; 5 next:point; 6 end; 7 8 var 9 i,j,k,l,m,n:longint;ll:int64; 10 a: array[ 0.. 1000000] of point; 11 c,b,d,e: array[ 0.. 1000500] of longint; 12 p:point; 13 procedure add(x,y,z:longint);inline; 14 var 15 p:point; 16 begin 17 new(p); 18 p^.g:=y; 19 p^.w:=z; 20 p^.next:=a[x]; 21 a[x]:=p; 22 end; 23 procedure bfs1;inline; 24 var 25 p:point;f,r:longint; 26 begin 27 b[ 1]:= 1;d[ 1]:= 1; 28 f:= 1;r:= 2; 29 while f<r do 30 begin 31 p:=a[d[f]]; 32 while p<> nil do 33 begin 34 if b[p^.g]= 0 then 35 begin 36 b[d[f]]:= 2; 37 b[p^.g]:= 1; 38 c[p^.g]:=d[f]; 39 d[r]:=p^.g; 40 inc(r); 41 end; 42 p:=p^.next; 43 end; 44 inc(f); 45 end; 46 end; 47 begin 48 readln(n); 49 for i:= 1 to n do a[i]:= nil; 50 for i:= 1 to n- 1 do 51 begin 52 readln(j,k,l); 53 add(j,k,l); 54 add(k,j,l); 55 end; 56 fillchar(b,sizeof(b), 0);ll:= 0; 57 fillchar(c,sizeof(c), 0);fillchar(d,sizeof(d), 0); 58 bfs1;ll:= 0; 59 for i:=n downto 1 do 60 begin 61 e[d[i]]:= 1; 62 p:=a[d[i]]; 63 while p<> nil do 64 begin 65 if p^.g<>c[d[i]] then 66 begin 67 ll:=ll+int64(abs(e[p^.g]-(n-e[p^.g])))*int64(p^.w); 68 e[d[i]]:=e[d[i]]+e[p^.g]; 69 end; 70 p:=p^.next; 71 end; 72 end; 73 writeln(ll); 74 readln; end .
DFS：
1 type 2 point=^node; 3 node=record 4 g,w:longint; 5 next:point; 6 end; 7 8 var 9 i,j,k,l,m,n:longint;ll:int64;10 a:array[0..1000000] of point;11 c,b:array[0..1000000] of longint;12 procedure add(x,y,z:longint);inline;13 var14 p:point;15 begin16 new(p);17 p^.g:=y;18 p^.w:=z;19 p^.next:=a[x];20 a[x]:=p;21 end;22 procedure dfs(x:longint);inline;23 var24 p:point;25 begin26 if b[x]=1 then exit;27 p:=a[x];b[x]:=1;28 while p<>nil do29 begin30 if b[p^.g]=0 then31 begin32 dfs(p^.g);33 ll:=ll+int64(int64(abs(int64(c[p^.g])-int64(int64(n)-int64(c[p^.g]))))*int64(p^.w));34 c[x]:=c[x]+c[p^.g];35 end;36 p:=p^.next;37 end;38 end;39 begin40 readln(n);41 for i:=1 to n do42 begin43 c[i]:=1;44 a[i]:=nil;45 end;46 for i:=1 to n-1 do47 begin48 readln(j,k,l);49 add(j,k,l);50 add(k,j,l);51 end;52 fillchar(b,sizeof(b),0);ll:=0;53 dfs(1);54 writeln(ll);55 end.