ABC026: C - 高橋君の給料

問題

C: 高橋君の給料 - AtCoder Beginner Contest 026 | AtCoder

解答

与えられた関係をグラフにすると木になるので、高橋くんから平社員めがけてDFSして計算する。

int N;
vector<vector<int>> G;
ll dfs(int curr) {
  ll mx = 0, mn = 1e18;
  rep(i, G[curr].size()) {
    int next = G[curr][i];
    ll a = dfs(next);
    mx = max(mx, a);
    mn = min(mn, a);
  }
  if (G[curr].empty()) {
    return 1;
  }
  return mx + mn + 1;
}

int main() {
  cin >> N;
  G.resize(N);
  rep(i, N - 1) {
    int b; cin >> b;
    G[b - 1].push_back(i + 1);
  }
  cout << dfs(0) << "\n";
}