fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define FOR(i, l, r) for (int i = l; i <= r; ++i)
  3. #define FOD(i, r, l) for (int i = r; i >= l; --i)
  4. #define ll long long
  5. #define ep emplace_back
  6. #define fi first
  7. #define se second
  8. #define pil pair <int, long long>
  9. #define NAME ""
  10. #define all(x) x.begin(), x.end()
  11.  
  12. using namespace std;
  13.  
  14. const int N = 1e5 + 5;
  15.  
  16. int n, k;
  17. vector <pil> adj[N];
  18. pil dp[N][2];
  19.  
  20. pil operator + (pil& a, pil b)
  21. {
  22.     return make_pair(a.fi + b.fi, a.se + b.se);
  23. }
  24.  
  25. void dfs(int u, int pa)
  26. {
  27.     int m = adj[u].size();
  28.     int z = (m - (u != 1));
  29.     vector <vector <pil>> f(z + 1, vector <pil> (k + 1, make_pair(0, 0)));
  30.     int i = 0;
  31.     for (int p = 0; p < m; ++p)
  32.     {
  33.         ll w = adj[u][p].fi;
  34.         int v = adj[u][p].se;
  35.         if (v == pa)
  36.             continue;
  37.         dfs(v, u);
  38.         ++i;
  39.         f[i][0] = f[i - 1][0] + dp[v][0];
  40.         FOR(j, 1, k)
  41.         {
  42.             f[i][j] = max(f[i][j - 1], f[i - 1][j] + dp[v][0]);
  43.             pil tmp = {1, -w};
  44.             tmp = tmp + f[i - 1][j - 1];
  45.             tmp = tmp + dp[v][1];
  46.             f[i][j] = max(f[i][j], tmp);
  47.         }
  48.     }
  49.     dp[u][0] = f[z][k];
  50.     dp[u][1] = f[z][k - 1];
  51. }
  52.  
  53. signed main()
  54. {
  55.     ios_base::sync_with_stdio(false);
  56.     cin.tie(NULL);
  57.     if (fopen(NAME".INP", "r"))
  58.     {
  59.         freopen(NAME".INP", "r", stdin);
  60.         freopen(NAME".OUT", "w", stdout);
  61.     }
  62.     cin >> n >> k;
  63.     FOR(i, 2, n)
  64.     {
  65.         int v;
  66.         ll w;
  67.         cin >> v >> w;
  68.         adj[v].ep(w, i);
  69.         adj[i].ep(w, v);
  70.     }
  71.     dfs(1, 1);
  72.     cout << dp[1][0].fi << ' ' << -dp[1][0].se;
  73.     return 0;
  74. }
Success #stdin #stdout 0.01s 6364KB
comments (?)
stdin
copy 
8 3
1 4
1 1
1 3
2 5
2 6
2 1
1 5
stdout
copy 
6 21
https://ideone.com/VAatOw
language:
C++ (gcc 8.3)
created:
22 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!