fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. #define SZ(X) ((int)(X).size())
  3. #define ALL(X) (X).begin(), (X).end()
  4. #define REP(I, N) for (int I = 0; I < (N); ++I)
  5. #define REPP(I, A, B) for (int I = (A); I < (B); ++I)
  6. #define RREP(I, N) for (int I= (N)-1; I>=0; --I)
  7. #define RREPP(I, A, B) for(int I = (B)-1; I>=A; --I)
  8. #define CASET int ___T, case_n = 1; scanf("%d ", &___T); while (___T-- > 0)
  9. #define MP make_pair
  10. #define PB push_back
  11. #define MS0(X) memset((X), 0, sizeof((X)))
  12. #define MS1(X) memset((X), -1, sizeof((X)))
  13. #define LEN(X) strlen(X)
  14. #define F first
  15. #define S second
  16. #define debug(A) REP(i, A.size()) cerr << A[i] << ' '; cerr << '\n'
  17. using namespace std;
  18.  
  19. typedef pair<int, int> ii;
  20. typedef vector<int> vi;
  21. typedef vector<vi> vvi;
  22.  
  23. typedef long long lld;
  24. typedef unsigned long long ulld;
  25. typedef pair<lld, lld> plld;
  26. typedef vector<lld> vlld;
  27. typedef vector<vlld> vvlld;
  28.  
  29. typedef long double ld;
  30. typedef vector<ld> vld;
  31. typedef vector<vld> vvld;
  32. const int MAXN=2015;
  33. const int INF=987654321;
  34. vvi linked; vi deleted, dfs;
  35. int T, N, M, Si[MAXN], Vi[MAXN], par[MAXN], size[MAXN], dp[MAXN][MAXN];
  36. void df(int root){
  37.     struct StackRes{ int here, iter; };
  38.     stack<StackRes> st; st.push({root, 0});
  39.     vi(1, root).swap(dfs); size[root]=1; par[root]=-1;
  40.     while(!st.empty()){
  41.         StackRes &top=st.top();
  42.         if(SZ(linked[top.here]) == top.iter){
  43.             if(par[top.here]!=-1) size[par[top.here]]+=size[top.here];
  44.             st.pop(); continue;
  45.         }
  46.         int there=linked[top.here][top.iter++];
  47.         if(deleted[there] || there==par[top.here]) continue;
  48.         st.push( { there, 0 });
  49.         par[there] = top.here; size[there] = 1; dfs.PB(there);
  50.     }
  51. }
  52. int solve(int root){
  53.     df(root); int sn = SZ(dfs), ret = 0;
  54.     for(int i=0;i<=M;i++) dp[sn][i] = -1; dp[sn][0]=0;
  55.     for(int i=sn-1;i>=0;i--){
  56.         int here = dfs[i];
  57.         for(int j=0;j<=M;j++){
  58.             dp[i][j]=dp[i+size[here]][j];
  59.             if(j>=Si[here] && dp[i+1][j-Si[here]] != -1)
  60.                 dp[i][j]=max(dp[i][j], dp[i+1][j-Si[here]]+Vi[here]);
  61.             if(i==0) ret=max(ret, dp[i][j]);
  62.         }
  63.     } return ret;
  64. }
  65. int dnc(int root){
  66.     df(root); int sn = SZ(dfs), mini=INF, minp;
  67.     // if(sn==1) return (Si[root]<=M ? Vi[root] : 0);
  68.     for(auto it : dfs) if( size[it] >= sn/2 && mini > size[it] ) mini=size[it], minp=it;
  69.     int ret = solve(minp); deleted[minp]=1;
  70.     for(auto it : linked[minp]) if(!deleted[it]) ret=max(ret, dnc(it));
  71.     return ret;
  72. }
  73. int main(){
  74.     int a,b;
  75.     ios::sync_with_stdio(false);
  76.     cin>>T;
  77.     while(T--){
  78.         cin>>N>>M;
  79.         vvi(N).swap(linked); vi(N).swap(deleted);
  80.         for(int i=0;i<N;i++) cin>>Si[i];
  81.         for(int i=0;i<N;i++) cin>>Vi[i];
  82.         for(int i=0;i<N-1;i++){
  83.             cin>>a>>b; a--;b--;
  84.             linked[a].PB(b); linked[b].PB(a);
  85.         }
  86.         cout<<dnc(0)<<"\n";
  87.     }
  88.     return 0;
  89. }
Success #stdin #stdout 0s 19128KB
comments (?)
stdin
copy 
1
9 7
1 1 3 2 1 1 1 5 5
1 0 8 5 1 2 0 9 14
1 2
2 3
2 4
3 5
3 6
4 7
4 8
7 9
stdout
copy 
15
https://ideone.com/Ntdepm
https://w...content-available-to-author-only...k.com/contests/w15/challenges/a-knapsack-problem
language:
C++14 (gcc 8.3)
created:
10 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!