MTREE - Another Tree Problem
Tác giả: RR
Ngôn ngữ: Pascal
{$R+,Q+}
{$M 1000000}
//{$Mode objFPC}
const
FINP='';
FOUT='';
MAXN=100001;
oo=1000000007;
type
list=^node;
node=record
u,c:longint;
next:list;
end;
var
f1,f2:text;
n:longint;
ke:array[1..MAXN] of list;
sum,sl:array[1..MAXN] of int64;
xet:array[1..MAXN] of longint;
kq:int64;
procedure openF;
begin
assign(f1,FINP); reset(f1);
assign(f2,FOUT); rewrite(f2);
end;
procedure closeF;
begin
close(f1); close(f2);
end;
procedure add(u,c:longint; var a:list);
var
p:list;
begin
new(p); p^.u:=u; p^.c:=c;
p^.next:=a; a:=p;
end;
procedure inp;
var
i,u,v,c:longint;
begin
read(f1,n);
for i:=1 to n-1 do
begin
read(f1,u,v,c);
add(u,c,ke[v]);
add(v,c,ke[u]);
end;
end;
procedure ans;
begin
if kq mod 2=0 then writeln(f2,kq div 2)
else writeln(f2,(kq+oo) div 2);
end;
procedure dfs1(u:longint);
var
v:longint;
c:int64;
p:list;
begin
xet[u]:=1;
sl[u]:=0; sum[u]:=0;
p:=ke[u];
while p<>nil do
begin
v:=p^.u; c:=p^.c; p:=p^.next;
if xet[v]=1 then continue;
dfs1(v);
sl[u]:=sl[u]+sl[v]+1;
sum[u]:=(sum[u]+c+sum[v]*c) mod oo;
end;
end;
procedure dfs2(u:longint);
var
v:longint;
x,y,c:int64;
p:list;
begin
xet[u]:=1;
p:=ke[u];
while p<>nil do
begin
v:=p^.u; c:=p^.c; p:=p^.next;
if xet[v]=1 then continue;
dfs2(v);
x:=(c*(sum[v]+1)) mod oo;
// try
y:=(sum[u]-(c*(sum[v]+1)) mod oo) mod oo;
// except writeln(c,' ',sum[v],' ',sum[u]); halt; end;
kq:=(kq+x*y) mod oo;
end;
kq:=(kq+sum[u]*2) mod oo;
end;
begin
openF;
inp;
dfs1(1);
fillchar(xet,sizeof(xet),0);
dfs2(1);
ans;
closeF;
end.