题解 | 派对的最大快乐值

#include<bits/stdc++.h>
using namespace std;

class TreeNode {
  public:
    int happy;
    vector<TreeNode*> next;
    TreeNode(int h): happy(h) {}
};

/*class Max {
  public:
    int no;
    int yes;
    Max(int n, int y): no(n), yes(y) {}
};*/

/*Max getMax(TreeNode* root) {
    if (root->next.empty()) return Max(0, root->happy);
    int n = 0, y = root->happy;
    for (auto r : root->next) {
        auto k = getMax(r);
        y += k.no;
        n += max(k.yes, k.no);
    }
    return Max(n, y);
}*/


struct ReturnType {
    int has_value;
    int no_value;
    ReturnType(int has, int no) {
        has_value = has;
        no_value = no;
    }
};


ReturnType dfs(TreeNode* root) {
    int has_res = root->happy;
    int no_res = 0;
    for (int i = 0; i < root->next.size(); ++i) {
        if (!root->next[i]) {
            continue;
        }
        ReturnType node = dfs(root->next[i]);
        has_res += node.no_value;
        no_res += max(node.has_value, node.no_value);
    }
    ReturnType res(has_res, no_res);
    return res;
}



int main() {
    int n, root;
    cin >> n >> root;
    vector<TreeNode*> happy(n);
    int t, u, v;
    for (int i = 0; i < n; ++i) {
        cin >> t;
        happy[i] = new TreeNode(t);
    }
    for (int i = 1; i < n; ++i) {
        cin >> u >> v;
        happy[u - 1]->next.push_back(happy[v - 1]);
    }
    auto res = dfs(happy[root - 1]);
    cout << max(res.has_value, res.no_value) << endl;
    //auto x = getMax(happy[root - 1]);
    //cout << max(x.no, x.yes) << endl;
    return 0;
}