deushiro

Untitled

Jan 26th, 2020
286
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.43 KB | None | 0 0
  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. vector <int> p;
  19.  
  20. int dfs(int v, int len) {
  21.     int maxi = len;
  22.     for (int u : g[v]) {
  23.         maxi = max(dfs(u, len + 1), maxi);
  24.     }
  25.     p[v] = maxi;
  26.     return maxi;
  27. }
  28.  
  29. void dfs2(int v, int len) {
  30.     if (g[v].size() == 0) {
  31.         ls.push_back(len);
  32.     }
  33.     int maxi = 0;
  34.     int res = 0;
  35.     for (int u : g[v]) {
  36.         if (p[u] > maxi) {
  37.             maxi = p[u];
  38.             res = u;
  39.         }
  40.     }
  41.     for (int u : g[v]) {
  42.         if (u != res)
  43.             dfs2(u, 1);
  44.         else
  45.             dfs2(u, len + 1);
  46.     }
  47. }
  48.  
  49.  
  50. int main()
  51. {
  52.     ios_base::sync_with_stdio(false);
  53.     cin.tie(0);
  54.  
  55.     int n, kk;
  56.     cin >> n >> kk;
  57.     int k = kk;
  58.     g.resize(n);
  59.     rg.resize(n);
  60.     used.resize(n);
  61.     p.resize(n);
  62.  
  63.     for (int i = 1; i < n; i++) {
  64.         int v;
  65.         cin >> v;
  66.         v--;
  67.         g[v].push_back(i);
  68.         rg[i].push_back(v);
  69.     }
  70.  
  71.     dfs(0, 1);
  72.     dfs2(0, 1);
  73.  
  74.  
  75.     sort(ls.begin(), ls.end());
  76.     reverse(ls.begin(), ls.end());
  77.  
  78.     ll ans = 0;
  79.     for (int i = 0; i < min(k, (int)ls.size()); i++)
  80.         ans += ls[i];
  81.     cout << ans;
  82. }
Advertisement
Add Comment
Please, Sign In to add comment