题解：
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.
网友评论