Advertisement
Guest User

Untitled

a guest
Sep 15th, 2019
245
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.93 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 1e5 + 5;
  5.  
  6. #define st first
  7. #define nd second
  8.  
  9. int n, k, a, ans, par[N], vis[N];
  10. pair<int, int> h[N];
  11. // height, who
  12. vector<int> adj[N];
  13. priority_queue<pair<int, int>> pq;
  14.  
  15. void dfs(int x, int p = -1){
  16.   par[x] = p;
  17.   pair<int, int> mx = {0, x};
  18.   for(auto v : adj[x])
  19.     if(v != p) dfs(v, x), mx = max(mx, h[v]);
  20.   h[x] = {mx.st + 1, mx.nd};
  21. }
  22.  
  23. void up(int x){
  24.   vis[x] = 1;
  25.   for(auto v : adj[x]) if(!vis[v] and v != par[x]) pq.push(h[v]);
  26.   if(par[x] != -1 and !vis[par[x]]) up(par[x]);
  27. }
  28.  
  29. int32_t main(){
  30.   ios_base::sync_with_stdio(0), cin.tie(0);
  31.   cin >> n >> k;
  32.   for(int i = 2; i <= n; i++) {
  33.     cin >> a;
  34.     adj[i].push_back(a);
  35.     adj[a].push_back(i);
  36.   }
  37.   dfs(1);
  38.   pq.push(h[1]);
  39.   for(int i = 0; i < k and pq.size(); i++){
  40.     pair<int, int> tp = pq.top();
  41.     pq.pop();
  42.     ans += tp.st;
  43.     up(tp.nd);
  44.   }
  45.   cout << ans << "\n";
  46. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement