题面描述

本题要求我们处理一个表示调用栈的树形结构，树的每个节点包含一个样本数量，节点间通过分隔符 -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(); // 关闭扫描器
    }
}

题目内容

调用栈指从主函数执行到某个函数的调用路径，

如 $A$->$B$ ，经过这条调用栈到达的其他调用栈称为其子调用栈，如 $A$->$B$->$D$ 是 $A$->$B$ 的子调用栈；

使用某性能分析工具对软件运行过程中的调用栈进行采样分析，得到的热点调用栈数据为树形结构。

树的每个节点代表一条调用栈，子节点为父节点的子调用栈，每个节点有一个数值为采样到该调用栈的样本数量。

现需要刷新各节点的数值为包含其子调用栈的总样本数量，请编码实现。

数的层序遍历，指的是从上到下遍历每层，每层从左到右遍历各节点；为了标识子节点关系，对于 $N$ 个节点的树的层序遍历，插入 $N$ 个 $-1$ ，第 $i$ 个 $-1$ 和第 $i+1$ 个 $-1$ 中间的节点序列为第 $i$ 个节点的子节点序列，根节点为第 $1$ 个节点;

输入描述

第一行为树的总节点数量 $N$ ，取值范围 $[1，1000]$ ；

第二行为树的序列化输入，采用层序遍历，共 $2N$ 个数据，包括 $N$ 个节点的样本数和 $N$ 个节点的子节点序列的分隔符(参见示例)；

各节点样本数取值范围 $[0，10000]$ ；

输出描述

输出刷新各节点数值后的树，与输入格式保持一致。

样例1

输入

6
5 -1 2 3 8 -1 -1 1 7 -1 -1 -1

输出

26 -1 2 11 8 -1 -1 1 7 -1 -1 -1

说明

第一行表示树一共有 $6$ 个节点:

第二行为按照层序遍历的序列化输入，共 $12$ 个数据(含 $6$ 个节点的样本数和 $6$ 个节点的子节点序列的分隔符)，含义分别为：

• 5：第一个节点(即根节点)样本数为5；
• -1：分隔第一个节点(即根节点)的子节点序列；
• 2：第二个节点的样本数为2，它是第一个节点(即根节点)的第一个子节点；
• 3：第三个节点的样本数为3，它是第一个节点(即根节点)的第二个子节点；
• 8：第四个节点的样本数为8，它是第一个节点(即根节点)的第三个子节点；
• -1：分隔第二个节点的子节点序列；后续无有效数值，表示该节点无子节点；
• -1：分隔第三个节点的子节点序列；
• 1：第五个节点的样本数为1，它是第三个节点的第一个子节点；
• 7：第六个节点的样本数为7，它是第三个节点的第二个子节点；
• -1：分隔第四个节点的子节点，后续无有效数值，表示该节点无子节点；
• -1：分隔第五个节点的子节点，后续无有效数值，表示该节点无子节点；
• -1：分隔第六个节点的子节点，后续无有效数值，表示该节点无子节点；

构造输入树形结构：

根据树形结构计算各节点包含子节点的样本数:

调用栈 $A$->$C$ 有子调用栈 $A$->$C$->$E$ 和 $A$->$C$->$F$ ，其包含子调用栈的样本数量为 $3+1+7=11$；

根节点调用栈 $A$ 包含了调用栈 $A$->$B$、$A$->$C$ 和 $A$->$D$，其包含子调用栈的样本数量为 $5+2+11+8=26$;

刷新后的热点调用栈树:

按照层序遍历序列化输出:

26 -1 2 11 8 -1 -1 1 7 -1 -1 -1