fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define mp make_pair
  3. #define pb push_back
  4. using namespace std;
  5.  
  6. vector <int> adj[200010];
  7.  
  8. struct costy
  9. {
  10.     int wt,val;
  11. };
  12. int g=1;
  13. int lo=0;
  14. int h=0;
  15. int K[605][12003];
  16. int ma=0;
  17. bool visited[1005];
  18. int W;
  19. int ar[1000]={0};
  20.  
  21. void dfs(costy lol[],int s)
  22. {
  23.     visited[s]=true;
  24.  
  25.     for(int i = 0;i < adj[s].size();++i)
  26.     {
  27.  
  28.         if(visited[adj[s][i]] == false)
  29.         {
  30.  
  31.             lo++;
  32.             ar[lo]=adj[s][i];
  33.             g++;
  34.             for (int w = 1; w <= W; w++)
  35.             {
  36.  
  37.                if (lol[ar[lo]].wt <= w)
  38.                      K[g][w] = max(lol[ar[lo]].val + K[g-1][w-lol[ar[lo]].wt],  K[g-1][w]);
  39.                else
  40.                      K[g][w] = K[g-1][w];
  41.             }
  42.             dfs(lol,adj[s][i]);
  43.             ma=max(ma,K[g][W]);
  44.             g--;
  45.             lo--;
  46.  
  47.         }
  48.     }
  49. }
  50.  
  51. int main()
  52. {
  53.     int n,m,i;
  54.     cin>>n;
  55.     for(i=0;i<=n;i++)
  56.         visited[i]=false;
  57.  
  58.     int k=n-1;
  59.     while(k--)
  60.     {
  61.         int x,y;
  62.         cin>>x>>y;
  63.         adj[x-1].pb(y-1);
  64.         adj[y-1].pb(x-1);
  65.  
  66.     }
  67.     costy lol[n+5];
  68.     for(i=0;i<n;i++)
  69.     {
  70.         cin>>lol[i].val;
  71.     }
  72.     for(i=0;i<n;i++)
  73.     {
  74.         cin>>lol[i].wt;
  75.     }
  76.     cin>>W;
  77.     for(i=0;i<=W;i++)
  78.         K[0][i]=0;
  79.     for(i=0;i<=n;i++)
  80.         K[i][0]=0;
  81.  
  82.     for (int w = 1; w <= W; w++)
  83.     {
  84.        if (lol[0].wt <= w)
  85.              K[g][w] = max(lol[0].val + K[g-1][w-lol[0].wt],  K[g-1][w]);
  86.        else
  87.              K[g][w] = K[g-1][w];
  88.     }
  89.     ma=max(ma,K[g][W]);
  90.     dfs(lol,0);
  91.     cout<<ma;
  92.     return 0;
  93. }
  94.  
Success #stdin #stdout 0s 34192KB
comments (?)
stdin
copy 
7
3 1
2 1
7 6
6 3
5 3
4 3
4 7 7 2 3 4 7
2 1 3 6 2 3 1
5
stdout
copy 
14
https://ideone.com/uenLZC
language:
C++ (gcc 8.3)
created:
7 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!