Codeforces Round #202 (Div. 1) B. Apple Tree

,

http://codeforces.com/contest/348/problem/B

解法

部分木ごとにbalancedな最大の重さを計算する。lcm。$O(V + E)$。

子である部分木が$l \ge 1$個あるとする。それぞれ重さ$w_i$を持ち、その重さを$p_i$刻みでしか変化させられないとする。 $p = {\rm lcm} \{ p_i \mid i \lt l \}$とすると、統合後の部分木のひとつあたりの重さ$w = \max \{ w \mid (\exists n. w = n \cdot p) \land (\forall i. w \le w_i) \}$。 この部分木全体では重さ$w \cdot l$で、$p \cdot l$刻みでしか変化できない。

実装

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
typedef long long ll;
using namespace std;
ll gcd(ll a, ll b) { if (b < a) swap(a,b); while (a) { ll c = a; a = b % c; b = c; } return b; }
ll lcm(ll a, ll b) { return (a * b) / gcd(a,b); }
int main() {
    int n; cin >> n;
    vector<ll> a(n); repeat (i,n) cin >> a[i];
    vector<vector<int> > g(n);
    repeat (i,n-1) {
        int x, y; cin >> x >> y; -- x; -- y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    function<pair<ll,ll> (int, int)> rec = [&](int i, int prv) {
        vector<ll> ws, ps;
        for (int j : g[i]) if (j != prv) {
            ll w, p; tie(w, p) = rec(j,i);
            ws.push_back(w);
            ps.push_back(p);
        }
        int l = ws.size();
        if (l == 0) return make_pair(a[i], 1ll);
        ll w = *min_element(ws.begin(), ws.end());
        ll p = 1; for (ll q : ps) {
            p = lcm(p, q);
            if (w < p) return make_pair(0ll, 1ll);
        }
        w = w / p * p;
        return make_pair(w * l, p * l);
    };
    ll ans = accumulate(a.begin(), a.end(), 0ll) - rec(0, -1).first;
    cout << ans << endl;
    return 0;
}