fork download
copy 
  1. // Bai 3
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef pair<int,int> ii;
  7.  
  8. constexpr int MAXN = 10000;
  9. constexpr int MAXS = 10000; // giới hạn tổng (kích thước bitset - 1)
  10.  
  11. int n, q;
  12. int c[MAXN + 5], w[MAXN + 5], par[MAXN + 5], ans[MAXN + 5];
  13. vector<int> adj[MAXN + 5];
  14. vector<int> splitv[MAXN + 5];
  15. bitset<MAXS + 1> dp[MAXN + 5];
  16. vector<pair<int,int>> queries[MAXN + 5];
  17.  
  18. void preDfs(int u, int p) {
  19.     par[u] = p;
  20.     for (int v : adj[u])
  21.         if (v != p) preDfs(v, u);
  22. }
  23.  
  24. void dfs(int u) {
  25.     dp[u].reset();
  26.     dp[u].set(0);
  27.  
  28.     for (int v : adj[u]) {
  29.         if (v == par[u]) continue;
  30.         dfs(v);
  31.  
  32.         // merge dp[v] into dp[u]
  33.         // use tmp = dp[u] (before merge) and for each set bit j in dp[v], do dp[u] |= tmp << j
  34.         bitset<MAXS + 1> tmp = dp[u];
  35.         const bitset<MAXS + 1> &dpv = dp[v];
  36.         for (size_t j = dpv._Find_first(); j < dpv.size(); j = dpv._Find_next(j)) {
  37.             if ((int)j > MAXS) break;
  38.             // shifting tmp by j; bits beyond MAXS are discarded automatically
  39.             dp[u] |= (tmp << j);
  40.         }
  41.         // also include sums that come solely from dp[v]
  42.         dp[u] |= dpv;
  43.     }
  44.  
  45.     // apply split (binary-split of multiplicities at node u)
  46.     for (int W : splitv[u]) {
  47.         if (W <= 0) continue;
  48.         dp[u] |= (dp[u] << W);
  49.     }
  50.  
  51.     // answer queries for node u
  52.     if (!queries[u].empty()) {
  53.         // queries[u] stored as {-S, idx} and sorted ascending, so -S ascending -> S descending
  54.         // we'll process them in order but maintain a pointer curMax to avoid repeated scans
  55.         int curMax = MAXS;
  56.         for (auto &qr : queries[u]) {
  57.             int S = -qr.first;
  58.             int idx = qr.second;
  59.             if (curMax > S) curMax = S;
  60.             while (curMax >= 0 && !dp[u].test(curMax)) --curMax;
  61.             // dp[u].test(0) should be true always, so curMax >= 0
  62.             ans[idx] = max(0, curMax);
  63.         }
  64.     }
  65. }
  66.  
  67. int main() {
  68.     ios::sync_with_stdio(false);
  69.     cin.tie(nullptr);
  70.  
  71.     if (fopen("MAIN.INP", "r")) {
  72.         freopen("MAIN.INP", "r", stdin);
  73.         freopen("MAIN.OUT", "w", stdout);
  74.     }
  75.  
  76.     if (!(cin >> n)) return 0;
  77.     for (int u = 1; u <= n; ++u) cin >> w[u] >> c[u];
  78.     for (int i = 1; i < n; ++i) {
  79.         int u, v; cin >> u >> v;
  80.         adj[u].push_back(v);
  81.         adj[v].push_back(u);
  82.     }
  83.  
  84.     // root tree at 1
  85.     preDfs(1, 0);
  86.  
  87.     cin >> q;
  88.     for (int i = 0; i < q; ++i) {
  89.         int u, S; cin >> u >> S;
  90.         queries[u].push_back({-S, i}); // store -S to sort descending S
  91.     }
  92.  
  93.     // prepare splits (binary decomposition of c[u] counts)
  94.     for (int u = 1; u <= n; ++u) {
  95.         sort(queries[u].begin(), queries[u].end()); // queries sorted by -S ascending -> S descending
  96.         int cnt = c[u];
  97.         for (int k = 1; k <= cnt; k <<= 1) {
  98.             splitv[u].push_back(k * w[u]);
  99.             cnt -= k;
  100.         }
  101.         if (cnt > 0) splitv[u].push_back(cnt * w[u]);
  102.     }
  103.  
  104.     dfs(1);
  105.  
  106.     for (int i = 0; i < q; ++i) cout << ans[i] << '\n';
  107.     return 0;
  108. }
  109.  
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/McdBfM
language:
C++14 (gcc 8.3)
created:
2 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!