题解 | 二叉树中的最大路径和

#include <climits>
#include <iostream>
#include <vector>
using namespace std;

// 以 root 为终点的最长路径
int dfs(int root, vector<int>& nums, vector<vector<int>>& children, int& res) {
    // 最长路，次长路
    int len1 = 0, len2 = 0;
    for (int child : children[root]) {
        int x = dfs(child, nums, children, res);
        if (x > len1) {
            len2 = len1;
            len1 = x;
        } else if (x > len2) {
            len2 = x;
        }
    }
    res = max(res, nums[root] + max(len1, 0) + max(len2, 0));
    return len1 + nums[root];
}

int main() {
    int n; cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    vector<vector<int>> children(n);
    for (int i = 0; i < n; i++) {
        int x; cin >> x;
        if (x > 0) {
            children[x - 1].push_back(i);
        }
    }

    int res = INT_MIN;
    dfs(0, nums, children, res);

    cout << res << endl;

    return 0;
}
// 64 位输出请用 printf("%lld")