fork(6) 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
stdin
6
2 3 5 1 4 3
1 2
1 3
2 4
3 5
3 6
stdout
10