对官方题解的优化：

1. 用不着MAX_NODES，根据输入n大小初始化tree和sample_count即可。
2. values已经是层序遍历的结果了。不用再重新层序遍历了，直接用更新后的值替换输入里非-1的结点值即可。

n = int(input())
values = list(map(int, input().split()))

sample_count = [0] * (n+1)
tree = [[] for _ in range(n+1)]

def dfs(current_node, parent_node):
    for child_node in tree[current_node]:
        if child_node == parent_node:
            continue
        dfs(child_node, current_node)
        sample_count[current_node] += sample_count[child_node]

def main():
    global n, values, sample_count, tree

    parent_node = 1
    child_node = 2
    sample_count[parent_node] = values[0]

    for value in values[1:]:
        if value == -1:
            parent_node += 1
        else:
            sample_count[child_node] = value
            tree[parent_node-1].append(child_node)
            tree[child_node].append(parent_node-1)
            child_node += 1

    dfs(1, 0)

    pos = 0
    updated_vals = sample_count[1:]
    for i, value in enumerate(values):
        if value == -1:
            continue
        else:
            values[i] = updated_vals[pos]
            pos += 1

    print(" ".join([str(x) for x in values]))

if __name__ == "__main__":
    main()

题面描述

本题要求我们处理一个表示调用栈的树形结构，树的每个节点包含一个样本数量，节点间通过分隔符 -1 来标识。输入包含树的节点总数和层序遍历的序列化数据，输出需要更新每个节点的样本数量，使其等于该节点自身的样本数量加上所有子节点的样本数量之和。通过解析输入构建树，计算新样本数量后，按相同格式输出更新后的数据。

思路

就是很简单的树的递归求和，$dfs$一遍即可，输入输出比较抽象注意处理

具体实现

1. 数据结构定义：

   • 使用 sampleCount 数组来存储每个节点的样本数量。
   • tree 是一个邻接表，用于存储树的结构，便于进行深度优先搜索（DFS）。
   • visited 数组用于标记节点是否被访问，以避免重复访问。

2. 输入处理：

   • 首先读取节点总数 n。
   • 然后，通过一个循环读取 2*n 个值，分别代表节点的样本数和分隔符 -1。如果读到 -1，则表示当前节点的子节点序列结束，准备进入下一个节点。
   • 代码使用两个索引 currentNodeIdx 和 childNodeIdx 来分别跟踪当前节点和子节点的索引，并建立节点之间的连接。

3. DFS 样本数量计算：

   • 通过 DFS 从根节点开始遍历整棵树。每当访问一个子节点时，将其样本数量累加到父节点的样本数量中。
   • 该过程保证了每个节点在计算时，其所有子节点的样本数量已被计算完成。

4. 输出格式化：

   • 输出根节点的样本数量后，按层序遍历的顺序输出每个节点的样本数量，节点之间通过 -1 进行分隔。
   • 在输出过程中，使用 visited 数组确保每个节点只输出一次。

5. 复杂度分析：

   • 时间复杂度为 O(N)，其中 N 为节点数，因为每个节点和边只被访问一次。
   • 空间复杂度也是 O(N)，主要是用于存储树结构和样本数量的数组。

cpp

#include <bits/stdc++.h>
using namespace std;

const int MAX_NODES = 1010; // 最大节点数量
int sampleCount[MAX_NODES]; // 每个节点的样本数量
int n; // 节点总数
vector<int> tree[MAX_NODES]; // 存储树的邻接表
bool visited[MAX_NODES]; // 访问标记，用于DFS

// 深度优先搜索（DFS）函数，计算每个节点包含子节点的样本总数
void dfs(int currentNode, int parentNode) {
    for (auto childNode : tree[currentNode]) {
        if (childNode == parentNode) continue; // 避免访问父节点
        dfs(childNode, currentNode); // 递归访问子节点
        sampleCount[currentNode] += sampleCount[childNode]; // 累加子节点的样本数
    }
}

int main() {
    cin >> n; // 读取节点总数
    int currentNodeIdx = 1; // 当前节点索引（从1开始）
    int childNodeIdx = 1; // 子节点索引（从1开始）
    
    for (int i = 1; i <= 2 * n; i++) {
        int value; // 当前输入的值
        cin >> value;
        if (value == -1) {
            currentNodeIdx++; // 进入下一个节点的子节点序列
        } else {
            sampleCount[childNodeIdx] = value; // 记录当前节点的样本数
            childNodeIdx++;
            // 连接当前节点与父节点（currentNodeIdx - 1）
            if (childNodeIdx > 2) { // 确保至少有一个子节点
                tree[currentNodeIdx - 1].push_back(childNodeIdx - 1); // 添加子节点
                tree[childNodeIdx - 1].push_back(currentNodeIdx - 1); // 添加父节点
            }
        }
    }

    dfs(1, -1); // 从根节点1开始进行DFS计算样本总数

    cout << sampleCount[1] << " " << -1 << " "; // 输出根节点的样本总数和分隔符
    visited[1] = true; // 标记根节点为已访问

    for (int i = 1; i <= n; i++) {
        int size = tree[i].size(); // 当前节点的子节点数量
        if (size > 1) { // 如果当前节点有多个子节点
            for (int j = 0; j < size; j++) {
                int childNode = tree[i][j]; // 当前子节点
                if (!visited[childNode]) { // 如果该子节点未被访问过
                    visited[childNode] = true; // 标记为已访问
                    cout << sampleCount[childNode] << " "; // 输出子节点的样本数
                }
            }
        }
        if (i != n) cout << -1 << " "; // 输出分隔符
    }

    return 0; // 程序结束
}

python

# 最大节点数量
MAX_NODES = 1010
# 每个节点的样本数量
sample_count = [0] * MAX_NODES
# 节点总数
n = 0
# 存储树的邻接表
tree = [[] for _ in range(MAX_NODES)]
# 访问标记，用于DFS
visited = [False] * MAX_NODES

# 深度优先搜索（DFS）函数，计算每个节点包含子节点的样本总数
def dfs(current_node, parent_node):
    for child_node in tree[current_node]:
        if child_node == parent_node:
            continue  # 避免访问父节点
        dfs(child_node, current_node)  # 递归访问子节点
        sample_count[current_node] += sample_count[child_node]  # 累加子节点的样本数

def main():
    global n
    n = int(input())  # 读取节点总数
    current_node_idx = 1  # 当前节点索引（从1开始）
    child_node_idx = 1  # 子节点索引（从1开始）

    # 读取所有输入值
    values = list(map(int, input().split()))

    for value in values:
        if value == -1:
            current_node_idx += 1  # 进入下一个节点的子节点序列
        else:
            sample_count[child_node_idx] = value  # 记录当前节点的样本数
            child_node_idx += 1
            # 连接当前节点与父节点（current_node_idx - 1）
            if child_node_idx > 2:  # 确保至少有一个子节点
                tree[current_node_idx - 1].append(child_node_idx - 1)  # 添加子节点
                tree[child_node_idx - 1].append(current_node_idx - 1)  # 添加父节点

    dfs(1, -1)  # 从根节点1开始进行DFS计算样本总数

    print(sample_count[1], -1, end=" ")  # 输出根节点的样本总数和分隔符
    visited[1] = True  # 标记根节点为已访问

    for i in range(1, n + 1):
        size = len(tree[i])  # 当前节点的子节点数量
        if size > 1:  # 如果当前节点有多个子节点
            for j in range(size):
                child_node = tree[i][j]  # 当前子节点
                if not visited[child_node]:  # 如果该子节点未被访问过
                    visited[child_node] = True  # 标记为已访问
                    print(sample_count[child_node], end=" ")  # 输出子节点的样本数
        if i != n:
            print(-1, end=" ")  # 输出分隔符

if __name__ == "__main__":
    main()  # 调用主函数

java

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    static final int MAX_NODES = 1010; // 最大节点数量
    static int[] sampleCount = new int[MAX_NODES]; // 每个节点的样本数量
    static List<Integer>[] tree = new ArrayList[MAX_NODES]; // 存储树的邻接表
    static boolean[] visited = new boolean[MAX_NODES]; // 访问标记，用于DFS
    static int n; // 节点总数

    // 深度优先搜索（DFS）函数，计算每个节点包含子节点的样本总数
    static void dfs(int currentNode, int parentNode) {
        for (int childNode : tree[currentNode]) {
            if (childNode == parentNode) continue; // 避免访问父节点
            dfs(childNode, currentNode); // 递归访问子节点
            sampleCount[currentNode] += sampleCount[childNode]; // 累加子节点的样本数
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt(); // 读取节点总数

        // 初始化邻接表
        for (int i = 0; i < MAX_NODES; i++) {
            tree[i] = new ArrayList<>();
        }

        int currentNodeIdx = 1; // 当前节点索引（从1开始）
        int childNodeIdx = 1; // 子节点索引（从1开始）

        for (int i = 1; i <= 2 * n; i++) {
            int value = scanner.nextInt(); // 当前输入的值
            if (value == -1) {
                currentNodeIdx++; // 进入下一个节点的子节点序列
            } else {
                sampleCount[childNodeIdx] = value; // 记录当前节点的样本数
                childNodeIdx++;
                // 连接当前节点与父节点（currentNodeIdx - 1）
                if (childNodeIdx > 2) { // 确保至少有一个子节点
                    tree[currentNodeIdx - 1].add(childNodeIdx - 1); // 添加子节点
                    tree[childNodeIdx - 1].add(currentNodeIdx - 1); // 添加父节点
                }
            }
        }

        dfs(1, -1); // 从根节点1开始进行DFS计算样本总数

        System.out.print(sampleCount[1] + " " + -1 + " "); // 输出根节点的样本总数和分隔符
        visited[1] = true; // 标记根节点为已访问

        for (int i = 1; i <= n; i++) {
            int size = tree[i].size(); // 当前节点的子节点数量
            if (size > 1) { // 如果当前节点有多个子节点
                for (int j = 0; j < size; j++) {
                    int childNode = tree[i].get(j); // 当前子节点
                    if (!visited[childNode]) { // 如果该子节点未被访问过
                        visited[childNode] = true; // 标记为已访问
                        System.out.print(sampleCount[childNode] + " "); // 输出子节点的样本数
                    }
                }
            }
            if (i != n) System.out.print(-1 + " "); // 输出分隔符
        }

        scanner.close(); // 关闭扫描器
    }
}