AtCoder Regular Contest 028 C - 高橋王国の分割統治

問題

　 $N$ 頂点の木に対して、各頂点についてその頂点を通らずに通行可能な頂点集合の最大の大きさを求めよ。

解法

　ある頂点を根としたときの答えを求めることを考える。根から行ける各頂点について、その頂点の下にいくつの頂点があるかを深さ優先探索で求め、それらのうち最大値が答えとなる。

　深さ優先探索で数を求めるとき、往復してしまうことを避けるために直前に通った頂点も状態として持つこととする(int dfs(int curr, int pre))。これはある辺に対応しており、メモ化することで $O(N - 1)$ で求めることができる。このとき $dfs(i, j) = N - dfs(j, i)$ であることを利用すると効率よく計算できる。

　答えを求める操作も辺の数を2方向に見るだけなので $O(2(N - 1))$ であり、結局 $O(2(N - 1)) = O(N)$ がこの問題全体を解くうえで必要な計算量となってこれは間に合う。実装においてはメモ化にmapを用いたのでさらに $log(2(N - 1))$ かかるがそれでも問題ない。

反省

　34分16秒(3WA)でAC。最初は眠くて頭が回っていなかったが、25分ごろに30点の部分点解法を出したときに、これをもうちょっと改造すればできそうだということに気が付いた。

　2回TLEを出しながらもなんとか適当な高速化をして通すことができたが、計算量がよくわからない。メモ化さえすれば高速化する前も $O(2N)$ に収まっているような気がしてしまうが……。 $dfs(i, j) = N - dfs(j, i)$ であることを利用することでそんなに変わるのだろうか。

　解説スライドを読むと木DPと言っている。解法が木DPと言われる問題は今のところそうと意識しないまま解けてしまっていることが何度かあるが、トポロジカル順が木構造に対応しているDPということだと理解している。

　これをテーブル形式で書けるというのが自分としては驚いてしまう。有向グラフとして扱い、 $N-1$ のものから考えているところがミソだということは言われればわかるが、これを解答として出せる気はしない。解ける限りは大人しくメモ化していいだろう。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

ll N;
vector<vector<ll>> connect;
map<pair<ll, ll>, pair<bool, ll>> memo;

ll dfs(ll curr, ll pre) {
    if (memo[{curr, pre}].first) {
        return memo[{curr, pre}].second;
    }
    memo[{curr, pre}].first = true;
    ll result = 1;
    for (ll next : connect[curr]) {
        if (next == pre) {
            continue;
        }
        result += dfs(next, curr);
    }
    memo[{pre, curr}].first = true;
    memo[{pre, curr}].second = N - result;
    return memo[{curr, pre}].second = result;
}

ll solve(ll curr) {
    ll ans = 0;
    for (ll next : connect[curr]) {
        ans = max(ans, dfs(next, curr));
    }
    return ans;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    cin >> N;
    connect.resize(N);
    for (ll i = 0; i < N - 1; i++) {
        ll p;
        cin >> p;
        connect[i + 1].push_back(p);
        connect[p].push_back(i + 1);
    }

    for (ll i = 0; i < N; i++) {
        cout << solve(i) << endl;
    }
}