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

Codeforces Round #202 (Div. 1) の練習会に参加しました。冴えてたというかなんと言うかで ABD を解けました。

問題

codeforces.com

解法

発想としては非常に単純です。

dp[v] = v 以下の部分木でバランスされている場合に, その部分木の最大りんご数

とします。ただ, これだけだと情報が足りないので,

dpdp[v] = v 以下の部分木で, りんご数は最低いくつの倍数になっていなければならないか

というのも考えます。例えば, 以下のような状況を考えます。

頂点 a には 3 つの子があり, その子の一つ b は 2 つの子を持っている

この時, b の頂点がバランスされているためには, b の 2 つの子のりんごの数は等しいので b の部分木は合計で 2 の倍数のりんごを持っています。また, 頂点 a は 3 つの頂点があるので, b が 2 の倍数であることを考慮すると a のりんごの数は 2*3 = 6 の倍数でなければなりません。

こんな感じで, 各部分木には, 「この部分木は g の倍数じゃなきゃだめですよー」的な制約がつくわけです。そのために dpdp が必要なわけですね。

こんな感じで dp と dpdp について考えます。v の各子が g1, g2, ..., gn の倍数でなければならないとすると, v の各子は g1, g2, ..., gn の倍数でなければならないので, 要するに g = LCM(g1, g2, ..., gn) とすると v の子はすべて g の倍数になっている必要があります。このもとで, なるべく各子の頂点数を少なくしたいので, 各子の頂点数は, もとの頂点数が p であるとすると,

p = p/g*g

とすれば良いわけです。また, dpdp[v] は,各子のりんご数が g の倍数で, そのような子が d 個あったとすると v のりんご数は d*g の倍数でなければなりません。ココらへんを上手いこと dfs すれば解けます。

const int MAXN = 100010;
vector<int> G[MAXN];
int a[MAXN];
ll MAX = 1e9+7;

pair<ll, ll> dfs(int v, int p) {
    vector<pair<ll, ll> > child;
    ll g = 1;
    bool leaf = true;
    for (int el : G[v]) {
        if (el == p) continue;
        leaf = false;
        child.push_back(dfs(el, v));
        ll tmp = child.back().second;
        if (g < MAX) {
            g = (g/__gcd(g, tmp)) * tmp;
        }
    }
    if (leaf) {
        return make_pair(a[v], 1);
    }
    if (g >= MAX) {
        return make_pair(0, MAX);
    } else {
        ll mini = MAX*100000;
        for (auto pp : child) mini = min(pp.first, mini);
        ll ret = mini/g*g;
        return make_pair(ret*child.size(), g*child.size());
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    ll sum = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        sum += a[i];
    }
    for (int i = 0; i < n-1; i++) {
        int x, y;
        cin >> x >> y;
        x--; y--;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    cout << sum-dfs(0, -1).first << endl;
    return 0;
}