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

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

int max(int a,int b){
    return a>b?a:b;
}

int main(){
    
    int mm = INT_MIN;
    int m;
    scanf("%d",&m);
    int a[m],fnode[m];
    int i,j;
    int n,cnt1,cnt2 ,val;
    int dp[m][3];
    for(i=0;i<m;i++){
        for(j=0;j<3;j++){
            dp[i][j]=mm;
        }
    }
    for(i=0;i<m;i++){
        scanf("%d",a+i);
        dp[i][0] = a[i];
    }
    for(i=0;i<m;i++){
        scanf("%d",fnode+i);
    }
    
    for(i=m-1;i>=0;i--){
        j=i;
        n=fnode[j];
        cnt1= max(0,dp[j][1]);
        cnt2=max(0,dp[j][2]);
        val=max(val,max(dp[j][0]+cnt1+cnt2,max(cnt1,cnt2)));
        if(n==0) break;
        cnt1=max(cnt1,cnt2)+dp[j][0];
        if(dp[n-1][1]<0){
            dp[n-1][1]=max(0,cnt1);
        
        }else{
            dp[n-1][2]=max(0,cnt1);
        }
        
    }
    
//    for(i=0;i<m;i++){
//        for(j=0;j<3;j++){
//            printf("%d\x20",dp[i][j]);
//        }
//        printf("\n");
//    }
//    
    if(m==1){
        printf("%d",a[0]);
    }else{
        printf("%d",val);
    }
    
    
    return 0;
}