fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define fi first
  3. #define se second
  4. #define int long long
  5. #define vi std::vector<int>
  6. #define isz(v) (int) v.size()
  7. #define pii std::pair<int, int>
  8. #define all(v) v.begin(), v.end()
  9. #define TIME 1.0 * clock() / CLOCKS_PER_SEC
  10. using namespace std;
  11. typedef long long ll;
  12.  
  13. const int MAXN = 5e3 + 7;
  14. const int inf64 = 1e15 + 7;
  15.  
  16. template <class X, class Y>
  17.     bool maximize(X &a, const Y &b){
  18.         if(a < b){
  19.             a = b;
  20.             return true;
  21.         }
  22.         return false;
  23.     }
  24.  
  25. template <class X, class Y>
  26.     bool minimize(X &a, const Y &b){
  27.         if(a > b){
  28.             a = b;
  29.             return true;
  30.         }
  31.         return false;
  32.     }
  33.  
  34. int f[MAXN][MAXN][2], n, t, lim[MAXN], val[MAXN], par[MAXN];
  35. int sz[MAXN];
  36. vector<int> a[MAXN], g[MAXN];
  37.  
  38. void dfsBuild(int u, int p){
  39.     sz[u] = 1;
  40.     for(auto v : a[u]){
  41.         if(v == p) continue;
  42.         par[v] = u;
  43.         dfsBuild(v, u);
  44.         sz[u] += sz[v];
  45.     }
  46. }
  47.  
  48. void dfs(int u, int p){
  49.     sz[u] = 1;
  50.     f[u][0][0] = f[u][0][1] = 0,
  51.     f[u][1][0] = f[u][1][1] = val[u];
  52.  
  53.     int lasNode = 0;
  54.  
  55.     for(int i = 1; i <= isz(g[u]) - 1; i++){
  56.         int v = g[u][i];
  57.         dfs(v, u);
  58.         sz[u] += min(sz[v], lim[v]);
  59.  
  60.  
  61.         for(int cntU = 0; cntU <= sz[u]; cntU++)
  62.             for(int cntV = 0; cntV <= min(sz[v], cntU); cntV++)
  63.                 maximize(f[v][cntU][1], f[g[u][i - 1]][cntU - cntV][1] + f[v][cntV][0]);
  64.  
  65.  
  66.         lasNode = v;
  67.     }
  68.  
  69.  
  70.     for(int cntU = 0; cntU <= lim[u]; cntU++)
  71.         maximize(f[u][cntU][0], f[lasNode][cntU][1]);
  72.  
  73. }
  74.  
  75. signed main() {
  76.     ios::sync_with_stdio(false);
  77.     cin.tie(nullptr);
  78.  
  79.     cin >> n;
  80.  
  81.     for(int i = 1; i <= n; i++)
  82.         cin >> lim[i] >> val[i], g[i].push_back(i);
  83.  
  84.     for(int i = 1; i <= n - 1; i++){
  85.         int x, y;
  86.  
  87.         cin >> x >> y;
  88.         a[x].push_back(y);
  89.         a[y].push_back(x);
  90.     } dfsBuild(1, -1);
  91.     for(int i = 2; i <= n; i++) g[par[i]].push_back(i);
  92.  
  93.     for(int i = 1; i <= n; i++)
  94.         sort(g[i].begin() + 1, g[i].end(), [&] (int x, int y){return sz[x] > sz[y];});
  95.  
  96.     memset(f, -0x3f, sizeof(f));
  97.     f[0][0][0] = f[0][0][1] = 0;
  98.  
  99.     dfs(1, -1);
  100.  
  101.     int ans = 0;
  102.  
  103.     for(int cnt = 0; cnt <= lim[1]; cnt++)
  104.         maximize(ans, f[1][cnt][0]);
  105.  
  106.     cout << ans;
  107.  
  108.     cerr << endl << "------------" << endl;
  109.     cerr << "Time: " << TIME << " s" << endl;
  110.     cerr << "------------" << endl;
  111.  
  112. }
  113.  
Success #stdin #stdout #stderr 0.07s 395760KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
------------
Time: 0.065734 s
------------
https://ideone.com/0vbOEq
language:
C++14 (gcc 8.3)
created:
15 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!