MTREE - Another Tree Problem
Tác giả: flashmt
Ngôn ngữ: Pascal
const fi='';
fo='';
maxn=100010;
z=1000000007;
var n:longint; re,s:int64;
a,c:array[1..maxn shl 1] of longint;
b:array[1..maxn,0..2] of longint;
pos,cur,sl:array[1..maxn] of longint;
procedure rf;
var i:longint;
begin
read(n);
for i:=1 to n-1 do
begin
read(b[i,0],b[i,1],b[i,2]);
inc(sl[b[i,0]]);
inc(sl[b[i,1]]);
end;
pos[1]:=1; cur[1]:=1;
for i:=2 to n+1 do
begin
pos[i]:=pos[i-1]+sl[i-1];
cur[i]:=pos[i];
end;
for i:=1 to n-1 do
begin
a[cur[b[i,0]]]:=b[i,1];
c[cur[b[i,0]]]:=b[i,2];
inc(cur[b[i,0]]);
a[cur[b[i,1]]]:=b[i,0];
c[cur[b[i,1]]]:=b[i,2];
inc(cur[b[i,1]]);
end;
end;
procedure visit(x,y:longint;var s:int64);
var i:longint; sq,t:int64;
begin
s:=0; sq:=0;
for i:=pos[x] to pos[x+1]-1 do
if a[i]<>y then
begin
visit(a[i],x,t);
t:=(t*c[i]) mod z;
re:=(re+(t*s) mod z) mod z;
s:=(s+t) mod z;
end;
re:=(re+s) mod z;
s:=(s+1) mod z;
end;
procedure pr;
var i:longint;
begin
re:=0;
visit(1,0,s);
writeln(re);
end;
begin
assign(input,fi); reset(input);
rf;
pr;
close(input);
end.