MTREE - Another Tree Problem

Tác giả: khuc_tuan

Ngôn ngữ: Pascal

//{$A8,B-,C+,D+,E-,F-,G+,H+,I+,J-,K-,L+,M-,N+,O+,P+,Q+,R+,S+,T-,U-,V+,W-,X+,Y+,Z1}
// {$APPTYPE CONSOLE}
 {$mode delphi}
{$M 16777216}

const
    modulo = 1000000007;

type
    List = class
        i, w : integer;
        n : List;
    end;

function POW(x,n : integer) : integer;
var
    t : integer;
begin
    if n=0 then begin POW := 1; exit; end;
    t := POW(x,n div 2);
    if n mod 2 = 0 then POW := int64(t) * t mod modulo
    else POW := int64(t) * t mod modulo * x mod modulo;
end;

procedure AddList(var l : List; i, w : integer);
var
    q : List;
begin
    q := List.Create;
    q.i := i;
    q.w := w;
    q.n := l;
    l := q;                
end;

var
    ke : array[1..100000] of List;
    i, u, v, w, n : integer;
    chia2 : integer;
    f, g : array[1..100000] of int64;
    father : array[1..100000] of integer;


procedure dfs(i : integer);
var
    p : List;
    z, j, w : integer;
    tong, tong2 : integer;
begin
    p := ke[i];
    tong := 0;
    tong2 := 0;
    while p<>nil do
    begin
        j := p.i;
        w := p.w;
        p := p.n;
        if father[i]<>j then
        begin
            father[j] := i;
            dfs(j);
            f[i] := (f[i] + f[j]) mod modulo;
            z := int64(w) * g[j] mod modulo;
            tong := (tong + z) mod modulo;
            tong2 := (tong2 + int64(z) * z mod modulo) mod modulo;
        end;
    end;

        g[i] := (tong + 1) mod modulo;
        f[i] := (f[i] + (int64(tong) * tong + modulo - tong2) mod modulo * chia2) mod modulo;
        f[i] := (f[i] + tong) mod modulo;
end;

begin
    chia2 := POW(2, modulo - 2);
    read(n);
    for i:=1 to n-1 do
    begin
        read(u,v,w);
        AddList(ke[u],v,w);
        AddList(ke[v],u,w);
    end;
    dfs(1);
    writeln(f[1]);
end.

Download