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

#include <bits/stdc++.h>
using namespace std;
vector<pair<int,vector<int>>>d(1010);
int n,k,ma=0xc0c0c0c0;
int dfs(int k)
{
    int res1=0,res2=0;
    if(!d[k].second.empty())res1=max(dfs(d[k].second[0]),0);
    if(d[k].second.size()==2)res2=max(dfs(d[k].second[1]),0);
    ma=max(ma,res1+res2+d[k].first);
    return max(res1,res2)+d[k].first;
}
int main() {
    d[0].first=0;
    cin>>n;
    for(int i=1;i<=n;i++)
    cin>>d[i].first;
    for(int i=1;i<=n;i++)
    {
        cin>>k;
        d[k].second.push_back(i);
    }
    dfs(d[0].second[0]);
    cout<<ma<<endl;
    return 0;
}