fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll = long long;
  5.  
  6. const ll oo = 1e18;
  7. const int N = 2005;
  8.  
  9. int n, sz[N], best_j[N][N][2];
  10. ll k, a[N], dp[N][N][2], next_dp[N][2];
  11. vector<int> adj[N], chosen;
  12.  
  13. void dfs(int u, int p) {
  14.     sz[u] = 1;
  15.     for (int i = 0; i <= n; i++) dp[u][i][0] = dp[u][i][1] = oo;
  16.     dp[u][0][0] = 0;
  17.     dp[u][1][1] = a[u];
  18.  
  19.     for (int v : adj[u]) {
  20.         if (v == p) continue;
  21.         dfs(v, u);
  22.  
  23.         int nsz = sz[u] + sz[v];
  24.         for (int i = 0; i <= nsz; i++) {
  25.             next_dp[i][0] = next_dp[i][1] = oo;
  26.         }
  27.  
  28.         for (int i = 0; i <= sz[u]; i++) {
  29.             for (int j = 0; j <= sz[v]; j++) {
  30.                 ll min_v = min(dp[v][j][0], dp[v][j][1]);
  31.                 if (dp[u][i][0] != oo && min_v != oo) {
  32.                     ll val0 = dp[u][i][0] + min_v;
  33.                     if (val0 < next_dp[i + j][0]) {
  34.                         next_dp[i + j][0] = val0;
  35.                         best_j[v][i + j][0] = j;
  36.                     }
  37.                 }
  38.                 if (dp[u][i][1] != oo && dp[v][j][0] != oo) {
  39.                     ll val1 = dp[u][i][1] + dp[v][j][0];
  40.                     if (val1 < next_dp[i + j][1]) {
  41.                         next_dp[i + j][1] = val1;
  42.                         best_j[v][i + j][1] = j;
  43.                     }
  44.                 }
  45.             }
  46.         }
  47.         sz[u] = nsz;
  48.         for (int i = 0; i <= sz[u]; i++) {
  49.             dp[u][i][0] = next_dp[i][0];
  50.             dp[u][i][1] = next_dp[i][1];
  51.         }
  52.     }
  53. }
  54.  
  55. void trace(int u, int p, int c, int st) {
  56.     for (int i = (int)adj[u].size() - 1; i >= 0; i--) {
  57.         int v = adj[u][i];
  58.         if (v == p) continue;
  59.  
  60.         int j = best_j[v][c][st];
  61.         int v_st = 0;
  62.         if (st == 0) {
  63.             if (dp[v][j][0] <= dp[v][j][1]) v_st = 0;
  64.             else v_st = 1;
  65.         } else v_st = 0;
  66.         trace(v, u, j, v_st);
  67.         c -= j;
  68.     }
  69.  
  70.     if (st == 1) chosen.push_back(u);
  71. }
  72.  
  73. void solve() {
  74.     cin >> n >> k;
  75.     for (int i = 1; i <= n; i++) cin >> a[i];
  76.     for (int i = 0; i < n - 1; i++) {
  77.         int u, v; cin >> u >> v;
  78.         adj[u].push_back(v);
  79.         adj[v].push_back(u);
  80.     }
  81.     dfs(1, 0);
  82.  
  83.     int ans = 0, best = 0;
  84.     for (int c = n; c >= 0; c--) {
  85.         ll min_w = oo;
  86.         int st = -1;
  87.         if (dp[1][c][0] <= k) { min_w = dp[1][c][0]; st = 0; }
  88.         if (dp[1][c][1] <= k && dp[1][c][1] < min_w) { min_w = dp[1][c][1]; st = 1; }
  89.  
  90.         if (st != -1) {
  91.             ans = c;
  92.             best = st;
  93.             break;
  94.         }
  95.     }
  96.  
  97.     if (ans > 0) trace(1, 0, ans, best);
  98.  
  99.     cout << ans << "\n";
  100.     sort(chosen.begin(), chosen.end());
  101.     for (int i = 0; i < (int)chosen.size(); i++)
  102.         cout << chosen[i] << " ";
  103.     cout << "\n";
  104. } 
  105.  
  106. int main() {
  107.     ios_base::sync_with_stdio(false); cin.tie(NULL);
  108.  
  109.     int tests = 1; // cin >> tests;
  110.     while (tests--) solve();
  111.  
  112.     #ifndef ONLINE_JUDGE
  113.     cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
  114.     #endif
  115.  
  116.     return 0;
  117. }
  118.  
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/koI6FK
language:
C++14 (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!