Submission #2484904

---

Source Code Expand

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <utility>
#include <cmath>
#include <iomanip>
#include <queue>
#include <map>
#include <set>
#include <random>
#include <sstream>
#include <stack>
#include <deque>

using namespace std;

#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vl;

int N;
vector<vi> G;
vector<map<int, int>> C;
vector<priority_queue<int>> ans;
vi sum;
vi used;

int dfs(int n) {
    int s = 1;
    used[n] = 1;
    for (int v : G[n]) {
        if (used[v]) {
            continue;
        }
        int c = 0;
        c = dfs(v);
        C[n][v] = c;
        ans[n].push(c);
        s += c;
    }
    sum[n] = s;
    return s;
}

int main() {
    cin >> N;
    G.resize(N);
    rep(i,N-1) {
        int p;
        cin >> p;
        G[i+1].push_back(p);
        G[p].push_back(i+1);
    }
    used.resize(N, 0);
    C.resize(N);
    ans.resize(N);
    sum.resize(N, 0);
    dfs(0);
    used.clear();
    used.resize(N, 0);
    queue<int> q;
    q.push(0);
    while (!q.empty()) {
        int n = q.front(); q.pop();
        if (used[n]) continue;
        used[n] = 1;
        for (int v : G[n]) {
            if (n) {
                int s = sum[v] - C[v][n];
                // for (auto a : C[v]) {
                //     if (a.first != n) {
                //         s += a.second;
                //     }
                // }
                // cout << n << " " << v << " " << C[n].count(v) << endl;
                if (!C[n].count(v)) {
                    C[n][v] = s;
                    sum[n] += s;
                }
                ans[n].push(s);
            }
            q.push(v);
        }
    }
    
    rep(i,N) cout << ans[i].top() << endl;

    return 0;
}

Submission Info

Judge Result