fork(8) download 
  1. #include <bits/stdc++.h>
  2.  
  3. const int maxn = 1e5 + 100; // n <= 100000 
  4.  
  5. int v[maxn]; // ensure v[i] <= 1e4, or else int won't work for dp
  6. int dp[maxn][2]; // dynamic programming answers
  7.  
  8. std::vector<int> G[maxn]; // graph for connections
  9.  
  10. void dfs(int x, int parent) {
  11.     for (int y: G[x]) {
  12.         if (y == parent) continue; 
  13.         dfs(y, x); // dfs all children
  14.     }
  15.  
  16.     int taking_x = v[x], not_taking_x = 0; // two cases for the values
  17.  
  18.     for (int y: G[x]) {
  19.         if (y == parent) continue;
  20.         taking_x += dp[y][true]; 
  21.         not_taking_x += dp[y][false]; 
  22.     }
  23.  
  24.     dp[x][true] = not_taking_x;  // if parent of x is taken, x is not taken
  25.     dp[x][false] = std::max(taking_x, not_taking_x);  //  if parent of x is not taken
  26. }
  27.  
  28. int main() {
  29.     // speed up cin/cout
  30.     std::ios::sync_with_stdio(false); std::cin.tie(0);
  31.  
  32.     /* input start */
  33.  
  34.     int n; std::cin >> n;
  35.  
  36.     for (int i = 1; i <= n; i++) {
  37.         std::cin >> v[i];
  38.     }
  39.  
  40.     for (int i = 1; i < n; i++) {
  41.         int x,y; std::cin >> x >> y;
  42.         G[x].push_back(y); G[y].push_back(x); 
  43.     }
  44.  
  45. 	/* input ends */
  46.  
  47.     dfs(1, -1); 
  48.  
  49.     std::cout << dp[1][false] << std::endl; // 1 never has its "parent" selected.
  50. }
Success #stdin #stdout 0s 5380KB
comments (?)
stdin 
6
2 3 5 1 4 3
1 2
1 3
2 4
3 5
3 6
stdout 
10
https://ideone.com/nVOzqL
language:
C++14 (gcc 8.3)
created:
7 years 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!