Submission #6514396

---

Source Code Expand

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

// types
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;

// macros
#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define FI first
#define SE second
#define REP(i,n) for(int i=0;i<((int)n);i++)
#define REP1(i,n) for(int i=1;i<((int)n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define PB push_back
#define EB emplace_back
#define MP(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL

// constants
const int inf = 1e9;
const ll linf = 1LL << 50;
const double eps = 1e-10;
const int mod = 1e9 + 7;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};



int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  
  ll n;
  cin >> n;
  
  vector<ll> b(n-1);
  REP(i, n-1)
    cin >> b[i];
  
  vector<pll> a(n, make_pair(-114514, 114514));
  REP(i, n-1){
    ll bill;
    if(a[n-1-i].FI == -114514)
      bill = 1;
    else
      bill = a[n-1-i].FI + a[n-1-i].SE + 1;
    
    ll boss = b[n-2-i]-1;
    if(a[boss].FI == -114514)
      a[boss].FI = a[boss].SE = bill;
    else{
      a[boss].FI = max(a[boss].FI, bill);
      a[boss].SE = min(a[boss].SE, bill);
    }
  }
  
  cout << a[0].FI + a[0].SE + 1 << endl;
  
}

Submission Info

Judge Result