Submission #3110460

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;
template<class T> void assign(V<T>& v, int n, const T& a = T()) { v.assign(n, a); }
template<class T, class... U> void assign(V<T>& v, int n, const U&... u) { v.resize(n); for (auto&& i : v) assign(i, u...); }

int rec(int v, const VV<>& c, V<>& a){
  if (c[v].empty()) return a[v] = 1;
  int res = 1;
  for (auto&& i : c[v]) res += rec(i, c, a);
  return a[v] = res;
}

int main() {
  cin.tie(NULL); ios::sync_with_stdio(false);
  int n; cin >> n;
  V<> p(n); for (int i = 1; i < n; i++) cin >> p[i];
  VV<> c(n);
  for (int i = 1; i < n; i++) c[p[i]].push_back(i);
  V<> a(n);
  rec(0, c, a);
  for (int i = 0; i < n; i++) {
    int res = -1;
    int s = 0;
    for (auto&& v : c[i]) {
      res = max(res, a[v]);
      s += a[v];
    }
    cout << max(res, n - 1 - s) << '\n';
  }
}

Submission Info

Judge Result