Advertisement
Guest User

Untitled

a guest
Jan 27th, 2020
126
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.50 KB | None | 0 0
  1. # include <bits/stdc++.h>
  2. # define FILE
  3. using namespace std;
  4.  
  5. const int N = 300015;
  6.  
  7. int n, k, ans = 0, p[N], deep[N], lc[N];
  8. int tree[4*N], ver[4*N];
  9. vector < int > gr[N];
  10.  
  11. void update( int x, int val, int tl = 1, int tr = n, int td = 1 ){
  12.     if( tl > tr || x > tr || tl > x ) return;
  13.     if( tl == tr ){
  14.         tree[td] = val;
  15.         ver[td] = x;
  16.     }
  17.     else{
  18.         int tm = ( tl+tr )>> 1;
  19.         update( x, val, tl, tm, td+td );
  20.         update( x, val, tm+1, tr, td+td+1 );
  21.         if( tree[td+td] > tree[td+td+1] ){
  22.             tree[td] = tree[td+td];
  23.             ver[td] = ver[td+td];
  24.         }
  25.         else{
  26.             tree[td] = tree[td+td+1];
  27.             ver[td] = ver[td+td+1];
  28.         }  
  29.     }
  30. }
  31. void dfs1( int v, int f ){
  32.     deep[v] = deep[f] + 1;
  33.     update( v,deep[v] );
  34.     for( auto to: gr[v] ){
  35.         if( to != v ){
  36.             dfs1( to, v );
  37.         }
  38.     }
  39. }
  40. void dfs2( int v, int f ){
  41.     if( lc[v] ) return;
  42.     lc[v] = 1;
  43.     deep[v] = 0;
  44.     update( v,deep[v] );
  45.     for( auto to: gr[v] ){
  46.         if( to != f ){
  47.             dfs1( to, v );
  48.         }
  49.     }
  50.     dfs2( p[v], v );
  51. }
  52.  
  53. int main(){
  54.  
  55.     # ifdef FILEs
  56.         freopen( "input.txt", "r", stdin );
  57.         freopen( "output.txt", "w", stdout );
  58.     # endif
  59.     ios_base::sync_with_stdio( false );
  60.     cin >> n >> k;
  61.     for( int i = 2; i <= n; i++ ){
  62.         cin >> p[i];
  63.         gr[p[i]].push_back( i );
  64.     }
  65.     lc[0] = 1;
  66.     deep[0] = 0;
  67.     dfs1( 1,0 );
  68.     int cnt = 0;
  69.  
  70.     for( int i = 1; i <= n; i++ ){
  71.         if( gr[i].size() == 0 )cnt++;
  72.     }
  73.  
  74.     k = min( k, cnt );
  75.     for(; k > 0; k -- ){
  76.         if( tree[1] == 1 ){
  77.             break;
  78.         }
  79.         ans += tree[1];
  80.         dfs2( ver[1], -1 );
  81.     }
  82.     ans += k;
  83.     cout << ans;
  84. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement