思路：遍历二叉树

把问题抽象出来，其实就是给定一颗二叉树，每个节点都有对应的权值，问从根节点出发到任意一个节点的路径之和的最大值。

可以使用DFS或者BFS求解，由于题目给的输入数据已经给定了各个节点的子节点的关系，对于下标为$i$的节点，它的左孩子的节点为$i*2$，右孩子的节点为$i*2+1$，但是，需要把下标映射到从1开始，才正确，具体参考下面代码

JavaScript

const readline = require('readline');

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});

let w = [0];  // 用于存储树节点值的数组，初始值为[0]
let n, res;  // 树的节点数和最大和

rl.on('line', (line) => {  // 当从输入流中读取一行数据时触发回调函数
  if (!n) {  // 如果节点数n未定义，说明是第一行输入
    w = w.concat(line.split(' ').map(Number));  // 将输入的字符串转换为数字并追加到数组w中
    n = w.length;  // 获取数组w的长度，即树的节点数
    res = 0;  // 初始化最大和为0

    function dfs(u, sum) {  // 定义深度优先搜索函数
      if (u >= n || w[u] === -1) {  // 如果节点索引超出范围或节点的值为-1（表示叶节点），则返回
        return;
      }
      res = Math.max(res, sum + w[u]);  // 更新最大和为当前最大和和当前路径和的最大值
      dfs(u * 2, sum + w[u]);  // 递归调用dfs函数，处理左子节点
      dfs(u * 2 + 1, sum + w[u]);  // 递归调用dfs函数，处理右子节点
    }

    dfs(1, 0);  // 调用深度优先搜索函数，从根节点开始，初始和为0
    console.log(res);  // 输出最大和
    rl.close();  // 关闭输入流
  }
})

C++

#include <iostream>
#include <vector>
#include <sstream> // 添加这行

using namespace std;

vector<int> w;  // 用于存储树节点值的数组
int n, res = 0;  // 树的节点数和最大和

void dfs(int u, int sum) {  // 深度优先搜索函数，接受两个参数：一个节点索引u和从根节点到当前节点的值之和sum
    if (u >= n || w[u] == -1) {  // 如果节点索引超出范围或节点的值为-1（表示叶节点），则返回
        return;
    }
    res = max(res, sum + w[u]);  // 更新最大和为当前最大和和当前路径和的最大值
    dfs(2 * u, sum + w[u]);  // 递归调用dfs函数，处理左子节点
    dfs(2 * u + 1, sum + w[u]);  // 递归调用dfs函数，处理右子节点
}

int main() {
    string input;
    getline(cin, input);  // 从标准输入读取一行
    stringstream ss(input);  // 使用字符串流处理输入
    int num;
    w.push_back(0);  // 在数组开头添加一个虚拟元素，使索引从1开始
    while (ss >> num) {
        w.push_back(num);  // 将读取的整数存入数组
    }
    n = w.size();  // 获取数组的长度，即树的节点数

    dfs(1, 0);  // 调用深度优先搜索函数，从根节点开始，初始和为0
    cout << res << endl;  // 输出最大和

    return 0;
}

Python

w=[0]+list(map(int,input().split()))  # 从输入中读取一个整数列表，并在列表开头添加一个0
n=len(w)  # 获取列表的长度
res=0  # 初始化一个变量来存储最大和

def dfs(u,sum):  # 定义一个函数dfs，它接受两个参数：一个节点索引u和从根节点到当前节点的值之和sum
    if u>=n or w[u]==-1:  # 如果节点索引超出范围或节点值为-1（表示叶节点），则返回
        return
    global res  # 使用全局变量res
    res=max(res,sum+w[u])  # 更新res为其当前值和sum加上当前节点值的最大值
    dfs(u*2,sum+w[u])  # 递归调用dfs函数，传入左子节点和更新后的sum
    dfs(u*2+1,sum+w[u])  # 递归调用dfs函数，传入右子节点和更新后的sum
    
dfs(1,0)  # 以初始和为0调用dfs函数，传入根节点
print(res)  # 打印最大和

Java

import java.util.Scanner;

public class Main {
    static int[] w;  // 用于存储树节点值的数组
    static int n;  // 树的节点数
    static int res = 0;  // 用于存储最大和的变量

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);  // 创建一个Scanner对象来读取输入
        String[] wStr = scanner.nextLine().split(" ");  // 读取一行输入并按空格分割成字符串数组
        n = wStr.length + 1;  // 计算树的节点数
        w = new int[n];  // 初始化存储节点值的数组

        for (int i = 1; i < n; i++) {
            w[i] = Integer.parseInt(wStr[i - 1]);  // 将字符串数组转换为整数并存入w数组
        }

        dfs(1, 0);  // 调用深度优先搜索函数，从根节点开始，初始和为0
        System.out.println(res);  // 打印最大和
    }

    static void dfs(int u, int sum) {
        if (u >= n || w[u] == -1) {  // 如果节点索引超出范围或节点的值为-1（表示叶节点），则返回
            return;
        }
        res = Math.max(res, sum + w[u]);  // 更新最大和为当前最大和和当前路径和的最大值
        dfs(2 * u, sum + w[u]);  // 递归调用dfs函数，处理左子节点
        dfs(2 * u + 1, sum + w[u]);  // 递归调用dfs函数，处理右子节点
    }
}

题目描述

给定一个二叉树，每个节点上站一个人，节点数字表示父节点到该节点传递悄悄话需要花费的时间。初始时，根节点所在位置的人有一个悄悄话想要传递给其他人，求二叉树所有节点上的人都接收到悄悄话花费的时间。

输入描述

给定二叉树

0 9 20 -1 -1 15 7 -1 -1 -1 -1 3 2

注：-1表示空节点

输出描述

返回所有节点都接收到悄悄话花费的时间

38

样例1

输入

0 9 20 -1 -1 15 7 -1 -1 -1 -1 3 2

输出

38