2017.07.14【NOIP提高组】模拟赛B组 灵能矩阵 题解

题解：

http://172.16.0.132/senior/#contest/show/2058/2

题目描述：

Protoss 的灵能矩阵由若干个节点所构成。它们构成了一棵有根树，树根为1 号节点。定义没有子节点的节点为叶节点。叶节点内储存着一定量的能量，而非叶节点的能量为它子树中所有叶节点的能量之和。
如果一个节点的每一个子节点的能量都相同，那么这个节点就是能量平衡的。如果矩阵内每一个节点都能量平衡，则这个矩阵是能量平衡的。
被你所接管的这个灵能矩阵，似乎在长期的废弃之后已经无法保持的能量的平衡。为了重新让矩阵平衡，你可以通过将叶节点储存的能量散逸到太空中。你不可以使一个叶节点储存的能量为负数。
你希望求出最少散逸多少能量到太空中就能使灵能矩阵的能量平衡。

输入：

第一行包含一个整数n，表示节点的数量。
接下来一行，包含A1,A2...An 这n 个非负整数，表示每个节点自身储存的能量。保证储存能量的节点都是叶节点。
接下来n -1 行，每行包含两个数字Si, Ti，描述一条从Si 号节点到Ti 号节点的边。

输出：

第一行包含一个整数，表示最少要散逸多少单位的能量才能使灵能矩阵的能量平衡。

样例输入：

6
0 0 12 13 5 6
1 2
1 3
1 4
2 5
2 6

样例输出：

6

数据范围限制：

对于15% 的数据，1<= n <= 10。
对于30% 的数据，对于边Si, Ti，Si + 1 ̸= Ti 的边数不超过3 条。
对于50% 的数据，1<= n <= 1000。
对于100% 的数据，1 <= n <= 100000，1 <= Ai <= 2^30。

分析：

Paste_Image.png

对于上图，假如我们要修改2号点，那么2号点消散的值要能被5,6号点分配掉，显然顺着贪心是不行的
我们设g[x]=lcm(g[x的儿子节点])*x的儿子个数，那么对于每一个的节点的儿子节点的能量会被修改成{(当前节点的儿子节点的最小能量值)-[(当前节点的儿子节点的最小能量值)%(g[当前节点]/当前节点的儿子节点的个数)]}
额……好像不太好理解，这样说吧，m=minn-minn%(g[x]/cnt)
那么对于每一个分支节点，要修改的值为原值-m，统计答案

用边集数组dg，否则会爆！！！

至于某些特别猥琐的原因，例如本人，打C的时候WA50，打P的时候AC，额……对不起无从解决sorry~

实现：

var
        n,i,x,y,tot:longint;
        s,nt,lt,t,ans,g:array[1..400000] of int64;
function gcd(x,y:longint):longint;
begin
        if y=0 then exit(x);
        exit(gcd(y,x mod y));
end;
function lcm(x,y:longint):longint;
begin
        exit(x*y div gcd(x,y));
end;
procedure dg(x:longint);
var
        i,y:longint;
        sum,min,cnt,m:int64;
begin
        i:=lt[x];
        g[x]:=1;
        sum:=0;
        cnt:=0;
        min:=maxlongint*maxlongint;
        while i>0 do
        begin
                y:=t[i];
                dg(y);
                g[x]:=lcm(g[x],g[y]);
                sum:=sum+s[y];
                if s[y]<min then min:=s[y];
                ans[x]:=ans[x]+ans[y];
                inc(cnt);
                i:=nt[i];
        end;
        if min<>maxlongint*maxlongint then
        begin
                g[x]:=g[x]*cnt;
                m:=min-min mod (g[x] div cnt);
                ans[x]:=ans[x]+sum-cnt*m;
                s[x]:=cnt*m;
        end;
end;
begin
        assign(input,'pylon.in');reset(input);
        assign(output,'pylon.out');rewrite(output);
        readln(n);
        for i:=1 to n do
        begin
                read(s[i]);
                if s[i]>0 then g[i]:=1;
        end;
        for i:=1 to n-1 do
        begin
                read(x,y);
            t[i]:=y;
        nt[i]:=lt[x];
        lt[x]:=i;
        end;
        dg(1);
        writeln(ans[1]);
        close(input);close(output);
end.