题目大意

在一个冒险类游戏中，参与者可以在一个由多个方格构成的地图上寻找食物。每个方格有一个编号、一个父方格编号和对应的食物单位数。参与者可以通过传送门从一个方格移动到另一个方格。 参与者可以选择任意方格作为起点，并可以在任何方格选择退出游戏。任务是计算参与者在退出时能够获得的最多食物单位数

思路

简单树上dp

1.数据结构设计：

使用邻接表来表示地图的结构，其中每个方格和其通过传送门可达的方格形成一个有向图。

2.输入处理：

读取方格的数量和每个方格的 id、parent-id、value，并构建邻接表。 确定根节点（parent-id 为 -1 的方格）。

3.深度优先搜索（DFS）：

使用 DFS 遍历整个树，从根节点开始，计算从每个方格出发可以获取的最多食物单位数。 对于每个方格，初始值为其自身的食物单位数。在访问子节点时，更新当前节点的食物总数为当前节点的食物数加上子节点的食物数。 在更新食物总数时，考虑子树的选择，可能会选择不访问某个子节点以达到更高的总和。

4.结果输出：

记录在 DFS 遍历过程中能获得的最大食物单位数，并在最后输出结果。

时间复杂度：$O(N)$

代码说明

整体代码流程

1.输入读取：

读取方格数量 N 和每个方格的 id、parent-id、value，构建树的邻接表。

2.邻接表构建：

使用数组或链表来存储每个方格可以通过传送门到达的其他方格。

3.DFS 初始化：

定义一个数组来存储每个方格可以获得的食物总和。 从根节点开始进行 DFS 遍历，计算每个节点的食物总和。

4.DFS 遍历：

递归访问每个方格，更新食物总数。 处理子节点并更新当前节点的食物总数。

5.输出结果：

输出参与者能够获得的最多食物单位数。

代码

CPP

#include <iostream>
#include <cstdio>
using namespace std;

const int maxn = 1e4 + 10; // 定义最大方格数量
int n; // 方格数量
int a[maxn], dp[maxn]; // a 用于存储每个方格的食物单位数，dp 用于存储从每个方格出发能获得的最多食物单位数
int head[maxn], ver[maxn << 1], Next[maxn << 1], tot = 1; // 图的邻接表
int ans = -1e9; // 初始化答案为负无穷大

// 添加边到邻接表
void add(int x, int y) {
    ver[++tot] = y; // 将 y 加入到 x 的邻接表
    Next[tot] = head[x]; // 记录原来的头节点
    head[x] = tot; // 更新头节点
}

// 深度优先搜索（DFS）
void dfs(int x) {
    dp[x] = a[x]; // 初始化当前节点的食物总数为其自身的食物单位数
    for (int i = head[x], y; i; i = Next[i]) { // 遍历当前节点的所有邻接节点
        y = ver[i]; // 获取邻接节点
        dfs(y); // 递归访问邻接节点
        dp[x] = max(dp[y] + a[x], dp[x]); // 更新当前节点的食物总数
        ans = max(ans, dp[x]); // 更新全局最大食物单位数
    }
}

int main() {
    scanf("%d", &n); // 读取方格数量
    int root; // 根节点
    for (int i = 0, x, y; i < n; ++i) { // 读取每个方格的信息
        scanf("%d %d", &x, &y); // 读取方格 id 和 parent-id
        scanf("%d", &a[x]); // 读取方格的食物单位数
        if (y != -1) add(y, x); // 如果 parent-id 不是 -1，添加边
        else root = x; // 否则记录根节点
    }
    dfs(root); // 从根节点开始 DFS
    printf("%d", ans); // 输出最大食物单位数
    
    return 0; // 程序结束
}

python

# 使用链式前向星存储图
def add(x, y):
    global tot
    ver.append(y)  # 将节点 y 添加到邻接表中
    Next.append(head[x])  # 将当前节点 x 的头指针保存到 Next 数组中
    head[x] = tot  # 更新节点 x 的头指针
    tot += 1  # 增加边的计数

# 深度优先搜索
def dfs(x):
    global ans
    dp[x] = a[x]  # 初始化当前节点的食物总数为其自身的食物单位数
    i = head[x]  # 从当前节点的头指针开始遍历
    while i:  # 只要 i 不为 0
        y = ver[i]  # 获取当前邻接节点
        dfs(y)  # 递归访问邻接节点
        dp[x] = max(dp[y] + a[x], dp[x])  # 更新当前节点的食物总数
        ans = max(ans, dp[x])  # 更新全局最大食物单位数
        i = Next[i]  # 移动到下一个邻接节点

# 主程序开始
n = int(input())  # 读取方格数量
maxn = 10010  # 最大方格数量
a = [0] * maxn  # 存储每个方格的食物单位数
dp = [0] * maxn  # 存储从每个方格出发可获得的最多食物单位数
head = [0] * maxn  # 邻接表头指针
ver = []  # 邻接表中的节点
Next = []  # 链式存储的下一条边
tot = 1  # 边的计数
ans = -1e9  # 初始化答案为负无穷大

# 读取每个方格的信息
root = 0  # 根节点
for _ in range(n):
    x, y = map(int, input().split())  # 读取方格 id 和 parent-id
    a[x] = int(input())  # 读取方格的食物单位数
    if y != -1:
        add(y, x)  # 如果 parent-id 不是 -1，添加边
    else:
        root = x  # 否则记录根节点

# 从根节点开始 DFS
dfs(root)
print(ans)  # 输出最大食物单位数

Java

import java.util.Scanner;

public class Main {
    static final int maxn = 10010; // 定义最大方格数量
    static int n; // 方格数量
    static int[] a = new int[maxn]; // 存储每个方格的食物单位数
    static int[] dp = new int[maxn]; // 存储从每个方格出发可获得的最多食物单位数
    static int[] head = new int[maxn]; // 邻接表的头指针
    static int[] ver = new int[maxn << 1]; // 存储邻接节点
    static int[] Next = new int[maxn << 1]; // 存储链式存储的下一条边
    static int tot = 1; // 边的计数
    static int ans = -1000000000; // 初始化答案为负无穷大

    // 使用链式前向星存储图
    static void add(int x, int y) {
        ver[++tot] = y; // 将节点 y 添加到邻接表中
        Next[tot] = head[x]; // 将当前节点 x 的头指针保存到 Next 数组中
        head[x] = tot; // 更新节点 x 的头指针
    }

    // 深度优先搜索
    static void dfs(int x) {
        dp[x] = a[x]; // 初始化当前节点的食物总数为其自身的食物单位数
        for (int i = head[x]; i != 0; i = Next[i]) { // 遍历当前节点的所有邻接节点
            int y = ver[i]; // 获取当前邻接节点
            dfs(y); // 递归访问邻接节点
            dp[x] = Math.max(dp[y] + a[x], dp[x]); // 更新当前节点的食物总数
            ans = Math.max(ans, dp[x]); // 更新全局最大食物单位数
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in); // 创建扫描器以读取输入
        n = scanner.nextInt(); // 读取方格数量
        int root = 0; // 初始化根节点
        for (int i = 0; i < n; i++) { // 读取每个方格的信息
            int x = scanner.nextInt(); // 读取方格 id
            int y = scanner.nextInt(); // 读取 parent-id
            a[x] = scanner.nextInt(); // 读取方格的食物单位数
            if (y != -1) { // 如果 parent-id 不是 -1，添加边
                add(y, x);
            } else { // 否则记录根节点
                root = x;
            }
        }
        dfs(root); // 从根节点开始 DFS
        System.out.println(ans); // 输出最大食物单位数
    }
}

Go

package main

import "fmt"

const maxn = 10010 // 定义最大方格数量

var (
	n      int              // 方格数量
	a      [maxn]int        // 存储每个方格的食物单位数
	dp     [maxn]int        // 存储从每个方格出发可获得的最多食物单位数
	head   [maxn]int        // 邻接表的头指针
	ver    [maxn << 1]int   // 存储邻接节点
	Next   [maxn << 1]int   // 存储链式存储的下一条边
	tot    = 1              // 边的计数
	ans    = -1000000000    // 初始化答案为负无穷大
)

// 使用链式前向星存储图
func add(x, y int) {
	ver[tot] = y              // 将节点 y 添加到邻接表中
	Next[tot] = head[x]       // 将当前节点 x 的头指针保存到 Next 数组中
	head[x] = tot             // 更新节点 x 的头指针
	tot++                     // 增加边的计数
}

// 深度优先搜索
func dfs(x int) {
	dp[x] = a[x] // 初始化当前节点的食物总数为其自身的食物单位数
	for i := head[x]; i != 0; i = Next[i] { // 遍历当前节点的所有邻接节点
		y := ver[i] // 获取当前邻接节点
		dfs(y)      // 递归访问邻接节点
		dp[x] = max(dp[y]+a[x], dp[x]) // 更新当前节点的食物总数
		ans = max(ans, dp[x]) // 更新全局最大食物单位数
	}
}

// 求最大值的辅助函数
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	fmt.Scan(&n) // 读取方格数量
	root := 0    // 初始化根节点
	for i := 0; i < n; i++ { // 读取每个方格的信息
		var x, y int
		fmt.Scan(&x, &y) // 读取方格 id 和 parent-id
		fmt.Scan(&a[x])  // 读取方格的食物单位数
		if y != -1 { // 如果 parent-id 不是 -1，添加边
			add(y, x)
		} else { // 否则记录根节点
			root = x
		}
	}
	dfs(root) // 从根节点开始 DFS
	fmt.Println(ans) // 输出最大食物单位数
}

Js

const maxn = 10010; // 定义最大方格数量
let n; // 方格数量
const a = new Array(maxn).fill(0); // 存储每个方格的食物单位数
const dp = new Array(maxn).fill(0); // 存储从每个方格出发可获得的最多食物单位数
const head = new Array(maxn).fill(0); // 邻接表的头指针
const ver = new Array(maxn << 1).fill(0); // 存储邻接节点
const Next = new Array(maxn << 1).fill(0); // 存储链式存储的下一条边
let tot = 1; // 边的计数
let ans = -1000000000; // 初始化答案为负无穷大

// 使用链式前向星存储图
function add(x, y) {
    ver[tot] = y; // 将节点 y 添加到邻接表中
    Next[tot] = head[x]; // 将当前节点 x 的头指针保存到 Next 数组中
    head[x] = tot; // 更新节点 x 的头指针
    tot++; // 增加边的计数
}

// 深度优先搜索
function dfs(x) {
    dp[x] = a[x]; // 初始化当前节点的食物总数为其自身的食物单位数
    let i = head[x]; // 从当前节点的头指针开始遍历
    while (i !== 0) { // 只要 i 不为 0
        const y = ver[i]; // 获取当前邻接节点
        dfs(y); // 递归访问邻接节点
        dp[x] = Math.max(dp[y] + a[x], dp[x]); // 更新当前节点的食物总数
        ans = Math.max(ans, dp[x]); // 更新全局最大食物单位数
        i = Next[i]; // 移动到下一个邻接节点
    }
}

// 主程序
function main() {
    const readline = require('readline'); // 引入 readline 模块
    const rl = readline.createInterface({
        input: process.stdin, // 设置输入流
        output: process.stdout // 设置输出流
    });

    // 读取方格数量 n
    rl.question('Enter the value of n: ', (value) => {
        n = parseInt(value); // 将输入值转换为整数

        let root = 0; // 初始化根节点
        const inputArr = []; // 用于存储输入行
        rl.prompt(); // 显示提示符
        rl.on('line', (line) => { // 监听输入行
            inputArr.push(line.trim()); // 去除行首尾空格并存入数组
            if (inputArr.length === n) { // 如果输入行数达到 n
                rl.close(); // 关闭输入流
            }
        }).on('close', () => { // 输入流关闭后的处理
            // 处理输入的方格信息
            for (let i = 0; i < n; i++) {
                const inputLine = inputArr[i].split(' '); // 分割输入行
                const x = parseInt(inputLine[0]); // 读取方格 id
                const y = parseInt(inputLine[1]); // 读取 parent-id
                a[x] = parseInt(inputLine[2]); // 读取方格的食物单位数
                if (y !== -1) { // 如果 parent-id 不是 -1，添加边
                    add(y, x);
                } else { // 否则记录根节点
                    root = x;
                }
            }
            dfs(root); // 从根节点开始 DFS
            console.log(ans); // 输出最大食物单位数
            process.exit(0); // 退出进程
        });
    });
}

main(); // 调用主程序

题目内容

小红设计的这个游戏是一个冒险类游戏，参与者需要在地图上寻找食物并获得尽可能多的食物，同时需要注意在游戏过程中所处的位置，因为不同的位置可以通过传送门到达其他位置，可能会影响食物获取的数量。

在游戏开始时，参与者会出发点选择一个方格作为起点，每个方格上至多 $2$ 个传送门，通过传送门可将参与者传送至指定的其它方格。每个方格上都标注了三个数字：id 、 parent-id 和 value 。其中， id 代表方格的编号， parent-id 代表可以通过传送门到达该方格的方格编号， value 代表在该方格获取或失去的食物单位数。

参与者需要在地图上行进，到达每个方格并获取或失去对应的食物单位数，直到满足退出游戏的条件之一。参与者的最终得分是所获取食物单位数的总和，需要尽可能地高。

需要注意的是地图设计时保证了参与者不可能到达相同的方格两次。因此，参与者当前所处的方格无传送门，游戏将立即结束。另外，参与者在任意方格上都可以宣布退出游戏，同样会结束游戏。

请计算参与者退出游戏后，最多可以获得多少单位的食物。

输入描述

第一行：方块个数 $N$ ( $N\le 10000$ )

接下来 $N$ 行，每行三个整数 id ， parent-id ， value ，具体含义见题面。

$0\le id,parent-id \lt N$ ， $-100\le value \le 100$

特殊的 parent-id 可以取 $-1$ 则表示没有任何方格可以通过传送门传送到此方格，这样的方格在地图中有且仅有一个。

输出描述

输出为一个整数，表示参与者退出游戏后最多可以获得多少单位的食物。

样例

样例1

输入

7
0 1 8
1 -1 -2
2 1 9
4 0 -2
5 4 3
3 0 -3
6 2 -3

输出

9

样例解释

参与者从方格 $0$ 出发，通过传送门到达方格 $4$ ，再通过传送门到达方格 $5$ 。一共获得 $8+(-2) +3=9$ 个单位食物，得到食物最多或者参与者在游戏开始时处于方格 $2$ ，直接主动宣布退出游戏，也可以获得 $9$ 个单位食物。

样例2

输入

3
0 -1 3
1 0 1
2 0 2

输出

5

样例解释

参与者从方格 $0$ 出发，通过传送门到达方格 $2$ ，一共可以获得 $3+2=5$ 个单位食物，此时得到食物最多。