AtCoder Grand Contest 009: B - Tournament

,

http://agc009.contest.atcoder.jp/tasks/agc009_b

solution

木DP。$O(N \log N)$。

数値$a_i$は人$i, a_i$が戦って$a_i$が勝ったことを示す。 つまりトーナメント中に次のような部分が存在する。

       a_i
        |
     .--+--.
     |     |
    a_i    i

優勝者は決まっているので、それぞれの人がどの順番で相手を倒したかしか自由度はない。 例えば$a_i = a_j = a$なら、次の図の*ijを配置する$2$通り。

           a
           |
        .--+--.
        |     |
        a     *
        |
     .--+--.
     |     |
     a     *

部分木の高さは低くて損しないので、木DPで下から決めていけばよい。

implementation

#include <algorithm>
#include <cstdio>
#include <functional>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
#define whole(x) begin(x), end(x)
using namespace std;

int main() {
    int n; scanf("%d", &n);
    vector<vector<int> > g(n);
    repeat (i, n - 1) {
        int a_i_1; scanf("%d", &a_i_1); -- a_i_1;
        g[a_i_1].push_back(i + 1);
    }
    vector<int> dp(n);
    function<void (int)> go = [&](int i) {
        if (g[i].empty()) return;
        vector<int> acc;
        for (int j : g[i]) {
            go(j);
            acc.push_back(dp[j]);
        }
        sort(whole(acc));
        reverse(whole(acc));
        repeat (k, acc.size()) acc[k] += k + 1;
        dp[i] = *max_element(whole(acc));
    };
    go(0);
    printf("%d\n", dp[0]);
    return 0;
}