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.

Download