两点间加的边的权值等于原树中两点间路径上各边的最大权值加1
这个结论很容易证明,如果比这个要小的话,那么就可以把那个路径上的最大边去掉,而采用更小的边,这样最小生成树就不是给定的了
for i := 1 to n - 1 do
with e[i] do readln(s, t, d);
sort(1, n - 1);
for i := 1 to n do begin
f[i] := i; g[i] := 1;
end;
for i := 1 to n - 1 do
with e[i] do begin
fs := find(s); ft := find(t);
tmp := g[fs] * g[ft];
ans := ans + tmp * (d + 1);
g[ft] := g[ft] + g[fs];
f[fs] := ft;
end;
writeln(ans - n + 1);
{$m 10000000}
program r366;
type
node=record u,v,w:Longint end;
var
e:array[1..20000]of node;
ans:qword;
x,y,n,i:Longint;
p,count:array[1..20000]of longint;
function getfather(v:longint):Longint;
begin
if p[v]<>v then p[v]:=getfather(p[v]);
exit(p[v]);
end;
procedure sort(l,r:longint);
var t:node;
i,j,mid:longint;
begin
i:=l; j:=r; mid:=e[(i+j)shr 1].w;
repeat
while e[i].w<mid do inc(i);
while e[j].w>mid do dec(j);
if i<=j then
begin
t:=e[i]; e[i]:=e[j]; e[j]:=t;
inc(i); dec(j);
end;
until i>j;
if i<r then sort(i,r);
if j>L then sort(l,j);
end;
begin
readln(n);
for i:=1 to n do
begin
p[i]:=i;
count[i]:=1;
end;
for i:=1 to n-1 do readln(e[i].u,e[i].v,e[i].w);
sort(1,n-1);
for i:=1 to n-1 do
begin
inc(ans,e[i].w);
x:=getfather(e[i].u);
y:=getfather(e[i].v);
inc(ans,(count[x]*count[y]-1)*(e[i].w+1));
p[x]:=y;
count[y]:=count[y]+count[x];
end;
writeln(ans);
end.