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

解题思路

• 二叉树遍历通常利用递归的思想，粗略地写了一版(链接前向星存图），令$ansans$表示二叉树中的最大路径和，$an{s}_{i}ans\_i$表示以$nod{e}_{i}node\_i$为节点的最大路径和，那么$ansans$必定是$an{s}_{i}ans\_i$中的某一个。
• 在遍历的过程中，对于任意一个节点$ii$的left分支和right分支,记录其较大者$mxmx$和较小者$mnmn$(注意不一定存在）,$ans=\max (ans,w_i,mx,w_i+mx,w_i+mn+mx)ans\; =\; \backslash max(ans,\; w\_i,mx,w\_i+mx,w\_i+mn\; +\; mx)$。
• 利用$d{p}_{i}dp\_i$记录经过$nod{e}_{i}node\_i$的到某一节点的较大分支，则有$d{p}_i=\max (dp[i],w_i+mx)dp\_i\; =\; \backslash max(dp[i],w\_i+mx)$，用于i的father计算经过其的最大路径和。
• 后续再给出优化的代码。

//粗糙的版本。
#include<bits/stdc++.h>
using namespace std;
struct edge{
    int to, next, w;
}es[100005];
int head[100005];
int ans = INT_MIN, cnt = 0;
void add_edge(int from, int to){
    es[++cnt].next = head[from];
    es[cnt].to = to;
    head[from] = cnt;
}
int dp[100005];
int weight[100005];
int solve(int i){
    if(dp[i] == INT_MIN) return dp[i];
    if(head[i] == 0) {
        dp[i] = weight[i];
        ans = max(ans, weight[i]);
        }
    else{
        int tmp;
        int mn = INT_MAX;
        int mx = INT_MIN;
        int cc = 0;
        for(int j = head[i]; j != 0; j=es[j].next){//利用cc记录分支的个数，如果cc为1，则路径中没有mn
            cc++;
            tmp = solve(es[j].to);
            mn = min(mn,tmp);
            mx = max(mx,tmp);
        }
        dp[i] = max(dp[i],weight[i] + mx);//记录经过i节点的最大分支。
        ans = max(ans, max(weight[i],max(mx+weight[i],max(mx+(cc<=1?0:mn)+weight[i],mx))));//寻求最大路径和
    }
    return dp[i];
}
int main(){
    int n;
    cin>>n;
    for(int i = 1; i <= n; ++i){
        cin>>weight[i];
    }
    int root;
    memset(dp,INT_MIN,sizeof(dp));
    for(int i = 1; i <= n; ++i){
        int tmp;
        cin>>tmp;
        if (tmp == 0) root = i;
        else{
            add_edge(tmp,i);
        }
    }
    solve(root);
    cout<<ans<<endl;
    return 0;
}