F. Dominant Indices | Educational Codeforces #47

再帰で解く。

とりあえず、d[x]は最大の深さの分まで求めればいい。それ以降は0が続くので。

頂点xのxを除くすべての子孫についてdが計算済みとして、d[x]を計算する。d[x]のすべての子供だけを見ればd[x]が求まる。つまり、すべての子供yについてd[x][i+1] += d[y][i], d[x][0] = 1とすればよい。これを愚直にやるとO(N²)の計算量がかかって間に合わない。

そこで、d[y][i]が最大になるような子供zについてd[z][i]に他のd[y][i]をマージしていき、d[x] = d[z]とする。大きい方から小さい方へのマージしていくことでO(NlogN)の計算量で済む。

計算量の説明。大きいグループへ小さいグループをマージする時、マージ後のグループの大きさは、元の小さいグループの大きさの2倍以上。よって、小さいグループのほうの各要素はO(logN)回のマージでNの大きさになる。よって全体でO(NlogN)の計算量になる。

d[x][i] = 0の部分の実装が楽そうなのでデックを使ったらMLEした。 dequeの実装は

c++ - What really is a deque in STL? - Stack Overflow

のようなのが一般的で

[C++] STLの型の使い分け

にあるように各メモリブロックのサイズは512バイトの実装だったりする。なので、グラフの問題でよく書く大量のvectorみたいな感じでdequeを大量に確保するとMLEしてしまう。つまり、今回の問題でいえば

deque<int> d[1000001];

みたいなのはだめ。代わりにd[x]はvectorに逆順に入れておく。

const int MA = 1000006;
vi G[MA], C[MA];
vector<vi> d;
int ans[MA], dominant[MA];

int f(int u, int p) {
    // leaf
    if (u != 1 && sz(G[u])==1) {
        d.push_back(vi{1});
        RT sz(d)-1;
    }

    int ma = 0, re = 0;
    each(v, G[u]) {
        if (v != p) {
            int id = f(v, u);
            if (sz(d[id]) > ma) {
                ma = sz(d[id]);
                re = id;
            }
            C[u].push_back(id);
        }
    }

    auto &a = d[re];
    int nd = sz(a);
    a.push_back(1);
    int &dom = ans[u];
    dom = dominant[re] + 1;
    ma = a[nd-dom];
    if (ma == 1)dom = 0;

    each(id, C[u]) {
        if (id != re) {
            auto &b = d[id];
            int nb = sz(b);
            rep(i, sz(b)) {
                a[nd-(i + 1)] += b[nb-1-i];
                if (a[nd-(i + 1)] > ma || (a[nd-(i + 1)] == ma && i + 1 < dom)) {
                    ma = a[nd-(i + 1)];
                    dom = i + 1;
                }
            }
        }
    }

    dominant[re] = dom;
    RT re;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20);

    int n;
    cin >> n;
    if (n <= 2) {
        rep(i, n)cout << 0 << endl;
        RT 0;
    }
    rep(i, n - 1) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    f(1, 0);
    for (int i = 1; i <= n; ++i) {
        cout << ans[i] << endl;
    }
}