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.

Download