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

#include <iostream>
#include<vector>
using namespace std;
using i64 =long long;
const int N =1e5+10;

i64 res =-1e9 ;

i64 dfs(int  root,vector<int> & val,vector<vector<int>>&tree)
{
    
    
    if(tree[root].size()==0)
    {
        res =max(res,1LL*val[root]);
        return val[root];
    }
    res =max(res ,1LL*val[root]);
    i64 mx =val[root];

    i64 x1 =-1e9,x2 =0;
    i64 sum =0;
    for(auto & node: tree[root])
    {
        i64 t =dfs(node,val,tree);
        x1= max(x1,t);
        sum+=t;
    }
    x2 = sum -x1;

    if(x1>0)mx+=x1;
    if(x2>0)mx+=x2;

    res =max(res,mx);
    //  cout<<res<<endl;
    return max(x1+val[root],1LL*val[root]);
}

int main() {
    int n ;
    cin>>n;
    vector<int> val(n+1);
    vector<vector<int>> tree(n+1);
    for(int i=1;i<=n;i++)cin>>val[i];
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        if(!x)continue;
        tree[x].push_back(i);
    }
    dfs(1,val,tree);
    cout<<res;
}
// 64 位输出请用 printf("%lld")