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

#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
int node[100001],dp[100001];
vector<int> vec[100001];
void dfs(int i){
    for(auto it : vec[i]){
        dfs(it);
        dp[i] = max(dp[i],dp[i] + dp[it]);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,ans = -1001;
    cin >> n;
    for(int i = 1;i <= n;++i){
        cin >> node[i];
        dp[i] = node[i];
    }
    for(int i = 1,f;i <= n;++i){
        cin >> f;
        vec[f].push_back(i);
    }
    dfs(0);
    for(int i = 1;i <= n;++i)
        ans = max(ans,dp[i]);
    cout << ans;
}