Submission #1380328

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const ull mod = 1e9 + 7;
#define REP(i,n) for(int i=0;i<(int)n;++i)
int N;

struct edge{
    int t, comp, rev;
    edge(int t, int comp, int rev): t(t), comp(comp), rev(rev){}
};

typedef vector<edge> Array;
typedef vector<Array> Graph;
Graph G(100005);
bool visit[100005];

int dfs(int now){
    visit[now] = true;
    int res = 1;
    REP(j, G[now].size()){
        int next = G[now][j].t;
        if(!visit[next]){
            int x = dfs(next);
            res += x;
            G[now][j].comp = x;
            int rev = G[now][j].rev;
            G[next][rev].comp = N - x;
        }
    }
    return res;
}

int main(){
    cin >> N;
    REP(i, N-1){
        int p;
        cin >> p;
        edge q(p, -1, G[p].size());
        edge r(i+1, -1, G[i+1].size());
        G[i+1].push_back(q);
        G[p].push_back(r);
    }

    dfs(0);

    REP(i, N){
        int res = -1;
        REP(j, G[i].size()){
            res = max(res, G[i][j].comp);
        }
        cout << res << endl;
    }
    return 0;
}

Submission Info

Judge Result