Ink Colors

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
  #define dbg(args...) { err("[dbg] ", args); }
#else
  #define dbg(args...)
#endif

void err() { cerr << endl; }
template<typename T, typename... Args>
void err(T a, Args... args) { cerr << a; err(args...); }

typedef long long ll;
typedef long double lf;
typedef pair<int,int> pii;

const int MAXN = 1e5 + 100;
const int oo = 1e8 + 100;
const int MOD = 1e9 + 7;
const lf EPS = 1e-9;

struct data { int u, f0, f1; };

int n;
vector<int> graph[MAXN];

int tc;
int seen[4][MAXN];
int dp[4][MAXN];

int best_change(const vector<data>& all, int used = -1) {
  int cnt = 2, ret = 0;
  for(auto& d : all) {
    if(cnt == 0) break;
    if(d.u == used) continue;
    ret += d.f0 - max(d.f0, d.f1);
    cnt--;
  }
  return cnt == 0 ? ret : -oo;
}

int go(int u, int lvl) {
  int& r = dp[lvl][u];
  if(seen[lvl][u] == tc) return r;
  seen[lvl][u] = tc;
  if(lvl == 0) {
    r = 0;
    for(auto& v : graph[u])
      r += max(go(v, 0), go(v, 1) + 1);
  } else {
    vector<data> all;
    int sum = 0;
    for(auto& v : graph[u]) {
      int f0 = go(v, 0), f1 = go(v, 1) + 1;
      all.push_back({v, f0, f1});
      sum += max(f0, f1);
    }
    sort(all.begin(), all.end(), [&](const data& d1, const data& d2) {
      return d1.f1 - d1.f0 < d2.f1 - d2.f0;
    });
    if(lvl == 1) {
      r = -oo;
      for(auto& d : all) {
        r = max(r, sum + (go(d.u, 2)-max(d.f0, d.f1)) + best_change(all, d.u));
      }
    } else {
      r = sum + best_change(all);
    }
  }
  return r;
}

int main() {
  #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
  #else
    // ios::sync_with_stdio(0); cin.tie(0);
    #define endl '\n'
  #endif

  for(tc = 1; scanf("%d", &n) == 1; ++tc) {
    for(int i = 1; i <= n; ++i) {
      graph[i].clear();
    }
    for(int i = 2; i <= n; ++i) {
      int p; scanf("%d", &p);
      graph[p].push_back(i);
    }
    printf("%d\n", go(1, 0));
  }

  return 0;
}