fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define N 510000
  3. using namespace std;
  4. vector<int>v[N];
  5. int n;
  6. int dfs(int x,int lim){
  7.     if(!v[x].size()){
  8.         return x>lim;
  9.     }
  10.     int num0=0,num1=0;
  11.     for(auto to:v[x]){
  12.         int tmp = dfs(to,lim);
  13.         if(tmp==0)num0++;
  14.         if(tmp==1)num1++;
  15.     }
  16.     if(num0<num1)return 1;
  17.     if(num1<num0)return 0;
  18.     return -1;
  19. }
  20. bool check(int lim){
  21.     return dfs(1,lim)<=0;
  22. }
  23. int main(){
  24.     std::ios::sync_with_stdio(0);
  25.     cin>>n;
  26.     for(int i=2;i<=n;i++){
  27.         int p;
  28.         cin>>p;
  29.         v[p].push_back(i);
  30.     }
  31.     int l=1,r=n,ans;
  32.     while(l<=r){
  33.         int mid=(l+r)>>1;
  34.         if(check(mid))ans=mid,r=mid-1;
  35.         else l=mid+1;
  36.     }
  37.     cout<<ans<<'\n';
  38.     return 0;
  39. }
Success #stdin #stdout 0.01s 15564KB
comments (?)
stdin
copy 
9
1 1 3 2 5 4 5 5
stdout
copy 
7
https://ideone.com/0USpxN
language:
C++14 (gcc 8.3)
created:
5 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!