题意概括

给定一个非空的二叉树，要求返回其最大路径和。

一条 路径 被定义为从树中任意节点出发，沿父子节点连接，达到任意节点的序列。该路径至少包含一个节点，且不一定需要经过根节点。

数据范围:

• $1 \le N \le 3 \times 10^4$ (节点个数)
• $-1000 \le \text{val} \le 1000$ (节点值)
• 输入以 1-based 索引表示节点关系。

基础知识

本题是树形动态规划的经典问题，通常通过 深度优先搜索 (DFS)，采用 后序遍历 的思想来解决。

对于树中的任意一个节点 u，我们需要考虑两种情况：

1. 以 u 为“拐点”的路径：这条路径连接了 u 的左子树、节点 u 本身、以及 u 的右子树，形成一个 "拱形"。这条路径的和为 u 的值 + 来自左子树的最大贡献 + 来自右子树的最大贡献。这种路径不能再向上延伸给 u 的父节点。我们用一个全局变量 ans 来不断更新这种路径的最大值。
2. 作为“链”一部分的路径：这条路径经过 u，并向上延伸到 u 的父节点。要使这条路径和最大，它只能包含 u 以及其左、右子树中贡献较大的那一条。这个值将作为递归函数的返回值，供父节点使用。

基于此，我们设计递归函数 dfs(u)：

• 返回值：函数返回以节点 u 为根的子树中，从 u 出发向下延伸的 单链 路径的最大和。计算方式为 u->val + max(0, max(dfs(u->left), dfs(u->right)))。我们取 max(0, ...) 是因为如果子树贡献为负，我们宁愿不选择该子树。
• 全局更新：在函数执行过程中，我们计算以 u 为“拐点”的路径和 u->val + max(0, dfs(u->left)) + max(0, dfs(u->right))，并用它来更新全局最大值 ans。

由于输入格式不是标准的指针形式，我们需要先根据输入信息（节点值、左右孩子索引）构建树的邻接关系，并找到根节点（没有作为任何其他节点的孩子的节点）。

算法的时间复杂度和空间复杂度均为 $O(N)$。

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

// 定义节点结构体
struct Nde {
    int v, l, r;
};

vector<Nde> t;
int ans;

// 深度优先搜索
int dfs(int u) {
    // base case: 空节点贡献为0
    if (u == -1) {
        return 0;
    }

    // 递归计算左右子树的单链最大路径和
    int lmx = dfs(t[u].l);
    int rmx = dfs(t[u].r);

    // 更新全局最大路径和 (以当前节点u为“拐点”)
    // 路径和 = 当前节点值 + 左子树贡献(非负) + 右子树贡献(非负)
    ans = max(ans, t[u].v + max(0, lmx) + max(0, rmx));

    // 返回从当前节点u出发向下的单链最大路径和
    return t[u].v + max(0, max(lmx, rmx));
}

void run() {
    int n;
    cin >> n;

    t.resize(n + 1);
    vector<bool> isr(n + 1, true); // isr[i] 判断i是否为根

    for (int i = 1; i <= n; ++i) {
        cin >> t[i].v >> t[i].l >> t[i].r;
        if (t[i].l != -1) {
            isr[t[i].l] = false;
        }
        if (t[i].r != -1) {
            isr[t[i].r] = false;
        }
    }

    int rt = -1;
    for (int i = 1; i <= n; ++i) {
        if (isr[i]) {
            rt = i;
            break;
        }
    }
    
    // 初始化ans为一个足够小的值
    ans = -2e9; 
    
    dfs(rt);
    cout << ans << endl;
}

int main() {
    // 关闭同步流
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    run();

    return 0;
}

/*
样例 1:
输入:
3
1 2 3
2 -1 -1
3 -1 -1
输出:
6

样例 2:
输入:
5
-10 2 3
2 9 -1
3 20 4 5
4 15 -1 -1
5 7 -1 -1
输出:
42
*/