Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- # include <bits/stdc++.h>
- # define FILE
- using namespace std;
- const int N = 300015;
- int n, k, ans = 0, p[N], deep[N], lc[N];
- int tree[4*N], ver[4*N];
- vector < int > gr[N];
- void update( int x, int val, int tl = 1, int tr = n, int td = 1 ){
- if( tl > tr || x > tr || tl > x ) return;
- if( tl == tr ){
- tree[td] = val;
- ver[td] = x;
- }
- else{
- int tm = ( tl+tr )>> 1;
- update( x, val, tl, tm, td+td );
- update( x, val, tm+1, tr, td+td+1 );
- if( tree[td+td] > tree[td+td+1] ){
- tree[td] = tree[td+td];
- ver[td] = ver[td+td];
- }
- else{
- tree[td] = tree[td+td+1];
- ver[td] = ver[td+td+1];
- }
- }
- }
- void dfs1( int v, int f ){
- deep[v] = deep[f] + 1;
- update( v,deep[v] );
- for( auto to: gr[v] ){
- if( to != v ){
- dfs1( to, v );
- }
- }
- }
- void dfs2( int v, int f ){
- if( lc[v] ) return;
- lc[v] = 1;
- deep[v] = 0;
- update( v,deep[v] );
- for( auto to: gr[v] ){
- if( to != f ){
- dfs1( to, v );
- }
- }
- dfs2( p[v], v );
- }
- int main(){
- # ifdef FILEs
- freopen( "input.txt", "r", stdin );
- freopen( "output.txt", "w", stdout );
- # endif
- ios_base::sync_with_stdio( false );
- cin >> n >> k;
- for( int i = 2; i <= n; i++ ){
- cin >> p[i];
- gr[p[i]].push_back( i );
- }
- lc[0] = 1;
- deep[0] = 0;
- dfs1( 1,0 );
- int cnt = 0;
- for( int i = 1; i <= n; i++ ){
- if( gr[i].size() == 0 )cnt++;
- }
- k = min( k, cnt );
- for(; k > 0; k -- ){
- if( tree[1] == 1 ){
- break;
- }
- ans += tree[1];
- dfs2( ver[1], -1 );
- }
- ans += k;
- cout << ans;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement