fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. typedef long double ld;
  5. typedef vector<int> vi;
  6. typedef vector<ld> vld;
  7. typedef vector<ll> vll;
  8. typedef vector<pair<ll, ll>> vp;
  9. typedef pair<int, int> pii;
  10. typedef pair<ll, ll> pll;
  11. #define fr first
  12. #define sc second
  13. #define all(a) a.begin(),a.end()
  14.  
  15.  
  16. void Hendi() {
  17.     ios_base::sync_with_stdio(0);
  18.     cin.tie(0);
  19.     cout.tie(0);
  20. #ifndef ONLINE_JUDGE
  21.     freopen("input.txt", "r", stdin);
  22.     freopen("output.txt", "w", stdout);
  23.     freopen("error.txt", "w", stderr);
  24. #endif
  25. }
  26.  
  27. const ll INF = 1e18;
  28. const ll MOD = 1e9 + 7;
  29. const double EPS = 1e-7;
  30. const int N = 1e4 + 5;
  31. const int N1 = 1e5 + 5;
  32. int dx[] = {0, 0, 1, -1, -1, -1, 1, 1};
  33. int dy[] = {1, -1, 0, 0, 1, -1, 1, -1};
  34. char di[] = {'R', 'L', 'D', 'U'};
  35.  
  36. ll mul(ll a, ll b) {
  37.     return ((a % MOD) * (b % MOD)) % MOD;
  38. }
  39.  
  40. ll sub(ll a, ll b) {
  41.     return ((a % MOD) - (b % MOD) + MOD) % MOD;
  42. }
  43.  
  44. ll add(ll a, ll b) {
  45.     return ((a % MOD) + (b % MOD)) % MOD;
  46. }
  47. int n , k;
  48. ll dp[N][25], dist[N], sz[N], in[N];
  49. vp adj[N];
  50.  
  51. ll dfs2(int p, int ch){
  52.     sz[ch] = 1;
  53.     for(auto &i : adj[ch]){
  54.         if(i.fr != p){
  55.             sz[ch] += dfs2(ch,i.fr);
  56.         }
  57.     }
  58.     return sz[ch];
  59. }
  60.  
  61. ll dfs(int p, int ch, int w){
  62.     dist[ch] = w;
  63.     for(auto &i : adj[ch]){
  64.         if(i.fr != p){
  65.             dist[ch] += dfs(ch,i.fr, i.sc);
  66.         }
  67.     }
  68.     return dist[ch];
  69. }
  70.  
  71. ll calc(int i , int tot){
  72.     if(i == n) return (tot == k? 0: -INF);
  73.     ll &ret = dp[i][tot];
  74.     if(~ret) return ret;
  75.     ret = 0;
  76.     if(i == 0 && adj[0].size() == 1 && k) ret = max(ret,calc(i + 1, tot + 1) + adj[0].back().sc);
  77.     if(sz[i] + tot <= k) ret = max(ret, calc(i + 1, tot + sz[i]) + dist[i]);
  78.     ret = max(ret, calc(i + 1, tot));
  79.     return ret;
  80. }
  81.  
  82. void solve() {
  83.     cin>> n >> k;
  84.     int x , y , w;
  85.     for (int i = 0; i < n; ++i) {
  86.         adj[i].clear();
  87.         dist[i] = 0;
  88.         sz[i] = 0;
  89.     }
  90.     for (int i = 0; i < n - 1; ++i) {
  91.         cin>> x >> y >> w;
  92.         adj[x].push_back({y,w});
  93.         adj[y].push_back({x,w});
  94.     }
  95.     memset(dp, - 1, sizeof dp);
  96.     dfs(-1,0,0);
  97.     dfs2(-1,0);
  98.     cout<< (dist[0] - calc(0, 0)) * 2 << endl;
  99. }
  100.  
  101. int main() {
  102.     Hendi();
  103.     int T = 1;
  104.     cin >> T;
  105.     while (T--) {
  106.         solve();
  107.     }
  108. }
Success #stdin #stdout 0.01s 5672KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/mgolXH
language:
C++ (gcc 8.3)
created:
1 day 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!