fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. #define FOR(i, j, k) for(int i = j; i <= k; i++)
  4. #define ROF(i, j, k) for(int i = j; i >= k; i--)
  5. #define INF 100000000
  6. #define MEM(n, val) memset(n, val, sizeof(n))
  7.  
  8. #define PB push_back
  9.  
  10. using namespace std;
  11.  
  12.  
  13. int n, q;
  14. vector<int> adjl[110], cost[110];
  15. int dp[110][110];
  16.  
  17.  
  18. int func(int u, int m, int par)  {
  19.     if(m == 0)    {
  20.         return 0;
  21.     }
  22.     if(adjl[u].size() == 1)    {
  23.         return -INF;
  24.     }
  25.     if(dp[u][m] != -1)    {
  26.         return dp[u][m];
  27.     }
  28.     int le_node, le_cost;
  29.     int ri_node, ri_cost;
  30.  
  31.     bool foo = 0;
  32.     FOR(i, 0, (int)adjl[u].size() - 1)   {
  33.         int v = adjl[u][i];
  34.         int c = cost[u][i];
  35.         if(v == par)    {
  36.             continue;
  37.         }
  38.         if(foo == 0)    {
  39.             le_node = v;le_cost = c;
  40.             foo++;
  41.         }
  42.         else    {
  43.             ri_node = v;ri_cost = c;
  44.             foo++;
  45.         }
  46.     }
  47.     int ans = -INF;
  48.  
  49.     FOR(k, 1, m - 1)   {
  50.         ans = max(ans, le_cost + ri_cost + func(le_node, (k) - 1, u) + func(ri_node, (m - k) - 1, u));
  51.     }
  52.     ans = max(ans, le_cost + func(le_node, m - 1, u));
  53.     ans = max(ans, ri_cost + func(ri_node, m - 1, u));
  54.  
  55.     //cout << u << " " << m << " : " << ans << "\n";
  56.     return dp[u][m] = ans;
  57.  
  58. }
  59.  
  60. int main()  {
  61.     //cin >> n >> s;
  62.     cin >> n >> q;
  63.     FOR(i, 1, n - 1)   {
  64.         int u, v, w;
  65.         cin >> u >> v >> w;
  66.         adjl[u].PB(v);
  67.         adjl[v].PB(u);
  68.         cost[u].PB(w);
  69.         cost[v].PB(w);
  70.     }
  71.     MEM(dp, -1);
  72.     cout << func(1, q, 0) << "\n";
  73.     return 0;
  74. }
  75. /**
  76. */
  77.  
Success #stdin #stdout 0s 15288KB
comments (?)
stdin
copy 
5 2
1 3 1
1 4 10
2 3 20
3 5 20
stdout
copy 
21
https://ideone.com/82fLVe
timus 1018
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

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!