Advertisement
OIQ

Untitled

OIQ
Jan 26th, 2020
164
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.97 KB | None
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <utility>
  5. #include <string>
  6. #include <math.h>
  7. #include <map>
  8. #include <set>
  9. #include <queue>
  10.  
  11. using namespace std;
  12.  
  13. typedef long long ll;
  14. vector <vector <int>> g;
  15. vector <vector <int>> rg;
  16. vector <int> used;
  17. vector <int> ls;
  18.  
  19. void dfs(int v, int len) {
  20.  
  21.     if (g[v].size() == 0){
  22.         ls.push_back(len);
  23.     }
  24.  
  25.     for (int i = 0; i < g[v].size(); i++) {
  26.         if (i != 0)
  27.             dfs(g[v][i], 1);
  28.         else
  29.             dfs(g[v][i], len + 1);
  30.     }
  31. }
  32.  
  33.  
  34. int main()
  35. {
  36.     ios_base::sync_with_stdio(false);
  37.     cin.tie(0);
  38.  
  39.     int n, kk;
  40.     cin >> n >> kk;
  41.     int k = kk;
  42.     g.resize(n);
  43.     rg.resize(n);
  44.     used.resize(n);
  45.  
  46.     for (int i = 1; i < n; i++) {
  47.         int v;
  48.         cin >> v;
  49.         v--;
  50.         g[v].push_back(i);
  51.         rg[i].push_back(v);
  52.     }
  53.  
  54.     dfs(0, 1);
  55.    
  56.  
  57.     sort(ls.begin(), ls.end());
  58.     reverse(ls.begin(), ls.end());
  59.  
  60.     ll ans = 0;
  61.     for (int i = 0; i < min(k, (int)ls.size()); i++)
  62.         ans += ls[i];
  63.  
  64.     cout << ans;
  65.    
  66.     return 0;
  67. }
Advertisement
RAW Paste Data Copied
Advertisement