fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define fi first
  3. #define se second
  4. #define all(v) v.begin() , v.end()
  5. #define sz(v) int(v.size())
  6. #define unq(v) sort(all(v)); v.resize(unique(all(v)) - v.begin());
  7. using namespace std;
  8.  
  9. typedef long long ll;
  10. typedef pair<int , int> ii;
  11. typedef pair<long long , int> lli;
  12.  
  13. const int maxN = int(2e5)+7;
  14. const int maxK = 107;
  15. const ll inf = ll(1e18)+7;
  16.  
  17. int n , k;
  18. pair<int , ll> dp[maxN][maxK] , tmp[maxK];
  19. pair<int , ll> base = {0 , inf};
  20. vector<ii> g[maxN];
  21.  
  22. pair<int , ll> calc(pair<int , ll> A , pair<int , ll> B){
  23.     if (A.fi < B.fi) swap(A , B);
  24.     if (A.fi == B.fi) A.se = min(A.se , B.se);
  25.     return A;
  26. }
  27.  
  28. void dfs(int u){
  29.     for (auto e : g[u]){
  30.         int v = e.fi;
  31.         dfs(v);
  32.     }
  33.     dp[u][0] = {0 , 0};
  34.     for (auto e : g[u]){
  35.         int v = e.fi;
  36.         int w = e.se;
  37.         for (int x = 0 ; x <= k ; x++) tmp[x] = base;
  38.         for (int x = 0 ; x <= k ; x++){
  39.             if (x > 0){
  40.                 pair<int , ll> val = {dp[u][x - 1].fi + dp[v][k - 1].fi + 1,  dp[u][x - 1].se + dp[v][k - 1].se + 1ll * w};
  41.                 tmp[x] = calc(tmp[x] , val);
  42.             }
  43.             pair<int , ll> val = {dp[u][x].fi + dp[v][k].fi ,  dp[u][x].se + dp[v][k].se};
  44.             tmp[x] = calc(tmp[x] , val);
  45.         }
  46.         for (int x = 0 ; x <= k ; x++) dp[u][x] = calc(dp[u][x] , tmp[x]);
  47.         for (int x = 1 ; x <= k ; x++){
  48.             dp[u][x] = calc(dp[u][x] , dp[u][x - 1]);
  49.         }
  50.     }
  51.     for (int x = 1 ; x <= k ; x++){
  52.         dp[u][x] = calc(dp[u][x] , dp[u][x - 1]);
  53.     }
  54. }
  55.  
  56. void solve(){
  57.     cin >> n >> k;
  58.     for (int i = 2 ; i <= n ; i++){
  59.         int x , w; cin >> x >> w;
  60.         g[x].push_back({i , w});
  61.     }
  62.     for (int i = 1 ; i <= n ; i++){
  63.         for (int j = 0 ; j <= k + 1 ; j++) dp[i][j] = base;
  64.     }
  65.     dfs(1);
  66.     cout << dp[1][k].fi << " " << dp[1][k].se << "\n";
  67. }
  68.  
  69. #define name "B"
  70.  
  71. int main(){
  72.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  73.     if (fopen(name".INP" , "r")){
  74.         freopen(name".INP" , "r" , stdin);
  75.         freopen(name".OUT" , "w" , stdout);
  76.     }
  77.     int t = 1; //cin >> t;
  78.     while (t--) solve();
  79.     return 0;
  80. }
  81.  
  82.  
Success #stdin #stdout 0.01s 9708KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 0
https://ideone.com/c5tNOu
language:
C++ (gcc 8.3)
created:
18 hours 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!