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

思路
对于二叉树种任一节点k，如果k作为某个路径上的一个点，这个路径的方向分两个方向：
1） 从节点k到k的父节点的方向。因为k的父节点dfs(par(k)))需要用到dfs(k)，需要返回这个方向上的值，需要从k的左右子树中选择大的(要和0比较，贪心)那个子树再加上val(k)
2） 不到k的父节点，也就是说路径在以k为根节点的子树中，计算路径和
3） 从情况1和情况2中去最大值更新答案
维护一个答案ans，保存最大路径和。给dfs根节点的编号1，一遍dfs之后ans就是答案

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

int n;
int val[N];
//sons[i]表示 节点序号i的孩子节点序号
vector<vector<int>> sons(N);
int ans = 0;
int dfs(int p){
    // 遍历每个子节点，找最大的
    int maxsub = 0;
    int tmp = 0;  //保存p的孩子 子树的路径和
    for(int x : sons[p]){
        int subv = dfs(x);
        maxsub = max(maxsub,max(subv, 0));
        tmp += max(0,subv);
    }
    ans = max(ans,max(val[p]+tmp, val[p]+maxsub));
    return val[p]+ maxsub;
}
int main() {
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> val[i];
    }
    int s = 0;
    for(int i = 1; i <= n; i++){
        cin >> s;
        sons[s].push_back(i);
    }
    if(n==1){
        cout << val[1] << endl;
        return 0;
    }
    dfs(1);
    cout <<ans << endl;
    return 0;
}
// 64 位输出请用 printf("%lld")