题目大意：

有一颗N个节点的树，每个叶子节点有一个权值，非叶子节点的权值为该节点的子节点的权值和。

我们可以使得叶子节点的权值减少一些(不定)，但是不能增加。现在有一个定义——平衡：当一个节点的所有子节点的权值相同时这个节点是平衡的，求使这棵树的所有节点平衡最少要减去的权值和

解题思路：

一开始我想的是由深度最大的节点开始，将同一深度的节点减权值到这一深度节点的最小权值

我发现这是错了，比如有一组数据：

6

0 0 1 1 9 9

1 2

1 3

1 4

2 5

2 6

我的代码输出17

正确答案应该为20

为什么是二十呢：

首先，深度为3的有5 6，5 6 的父亲是2，5 6权值相同，然后2就是平衡的

然后深度为2的有2， 3， 4，权值分别为：18 1 1

我的程序将2的权值减去17，然后这一层就相同了

但是我们发现，当2的权值减去17，剩下1时，5 6的权值就不相同(2的权值 = 5的权值 + 6的权值 = 1)

所以就是错的

于是我们就要维护一个g[x]表示假如把x这个点改成m，那m应该是g[x]的倍数。

那么这个g[x]应该怎么求呢，应该是（所有g[son]的lcm）*（son的个数），想想为什么，因为我们要是我们这个被分下去的数要满足是自己son数的个数，还要满足是自己son的son的个数……这样下去，就是lcm咯~

于是我们就可以做了，每次我们设把这一排子节点改成m，然后m就应该是=min(son中最小的一个)-min mod (g[x]son的个数g[x]son的个数)，为什么呢，因为我们要满足它只能减，不能加，所以要取最小的，然后又要是g[x]的倍数，所以就要减去它们的余数，就可以整除了，最优一次次累加，就得到了ans~~

——引自

Accepted code:

#include
    
     #include
     
      #include
      
       #include
       
        #define maxn 200005#define ll long longstruct edge {
    ;    ll to, next;}e[maxn];ll ls[maxn], n, a[maxn], son[maxn];ll ans = 0;bool v[maxn];inline ll read() {
        ll x = 0; char c = getchar();    while (!isdigit(c)) c = getchar();    while (isdigit(c)) x = (x<<1) + (x<<3) + c -'0', c = getchar();    return x;}ll gcd(ll a, ll b) {
        return b == 0 ? a : gcd(b, a%b);}ll lcm(ll a, ll b) {
        return a / gcd(a, b) * b;}void wodefuck(ll now) {
        v[now] = 1;    if (a[now] != 0) {
            son[now] = 1;        return;    }    ll tot = 0, minn = 9e18, sum = 0;    son[now] = 1;    for (ll i = ls[now]; i; i = e[i].next)        if (!v[e[i].to]) {
                wodefuck(e[i].to);            sum += a[e[i].to];            tot++;            minn = std::min(minn, a[e[i].to]);            son[now] = lcm(son[e[i].to], son[now]);        }    son[now] *= tot;    ll m = minn - (minn % (son[now] / tot));    ans += sum - m * tot;    a[now] = m * tot;    return;}signed main() {
        /*freopen("pylon.in", "r" ,stdin);    freopen("pylon.out", "w", stdout);*/    n = read();    for (ll i = 1; i <= n; i++)        a[i] = read();    ll l = 0;    for (ll i = 1; i < n; i++) {
            ll x = read(), y = read();        e[++l] = (edge){
    y, ls[x]};        ls[x] = l;        e[++l] = (edge){
    x, ls[y]};        ls[y] = l;    }    wodefuck(1);    printf("%lld\n", ans);}