1. 问题描述：
给定一棵 n 个节点组成的树。树中节点编号为 1∼n，1 号节点为树的根节点。树中的每个节点 v 都具有一个非负整数权值 av。我们用 sv 来表示从节点 v 到根节点的路径上经过的所有节点（包括两端节点）的权值之和；用 hv 来表示从节点 v 到根节点的路径上经过的所有节点（包括两端节点）的数量，显然，s1 = a1，h1 = 1。现在，我们只知道树的具体结构以及所有 h 值为奇数的节点的 s 值。请你为树中的每个节点 v 赋予一个非负整数权值 av，要求在满足已知信息的情况下，所有节点的权值之和 ∑i=1n ai 尽可能小，输出 ∑i=1n ai 的最小可能值。
输入格式
第一行包含一个整数 n，第二行包含 n − 1 个整数 p2，p3，…，pn，其中 pi 表示节点 i 的父节点编号，第三行包含 n 个整数 s1，s2，…，sn，注意，由于所有 h 值为偶数的节点的 s 值都是未知的，所以这些节点的 s 值并未直接给出，而是用 −1 来代替
输出格式
一个整数，表示 ∑i=1nai 的最小可能值，如果不存在任何满足已知信息的合理赋值方案，则输出 −1。
数据范围
前 4 个测试点满足 2 ≤ n ≤ 5
所有测试点满足 2 ≤ n ≤ 10 ^ 5，1 ≤ pi < i，−1 ≤ si ≤ 10 ^ 9
输入样例1：
5
1 1 1 1
1 -1 -1 -1 -1
输出样例1：
1
输入样例2：
5
1 2 3 1
1 -1 2 -1 -1
输出样例2：
2
输入样例3：
3
1 2
2 -1 1
输出样例3：
-1
来源：
2. 思路分析：
我们可以先考虑一棵树的局部，如下图所示当前节点 p 为偶数节点，a1，a2，a3，a4 为奇数节点，则 a2 + ap = S2 – S1，a3 + ap = S3 – S1，a4 + ap = S4 – S1，而 a2，a3，a4 均大于等于 0 所以 ap <= S2 – S1，ap <= S3 – S1，ap <= S4 – S1，而 a2 + a3 + a4 + ap = S2 – S1 + S3 – S1 + S4 – S1 – 2ap，Si 是一个定值所以要想使得 a2 + a3 + a4 + ap 最小应该需要使 ap 最大，结合上面 ap 需要满足的限制那么 ap 等于 min(S2 – S1，S3 – S1，S4 – S1)，然后我们考虑整体，局部的值为 a2 + a3 + a4 + ap = S2 – S1 + S3 – S1 + S4 – S1 – 2ap， 所以核心是偶数节点的权值，而局部与局部的奇数节点的权值之和是确定的，所以他们相减的差值也是确定的，也即他们之间是相互独立的那么只需要考虑每一个局部就可以，所以我们使得每一个局部的 ap 最小那么整棵树的权值之和就是最小的；我们在遍历树中节点的时候可以传递一个当前递归深度的变量，如果 depth 为奇数那么往下递归，如果为偶数那么往下递归之后计算出当前的 ap 值，ap 确定之后那么 ap 的邻接点也是的权值也是确定的，每一次将局部的 ap，a[next] 的权值累加到答案中即可，由于第一个根节点没有局部所以需要将第一个根节点的值累加到答案中：
3. 代码如下：
python（超时）：
import sys
from typing import List
class Solution:
res = None
INF = 10 ** 18
def dfs(self, u: int, depth: int, last_s: int, s: List[int], g: List[List[int]]):
# depth%2==1说明当前节点u是奇数节点不同处理往下递归就行
if depth % 2:
for next in g[u]:
self.dfs(next, depth + 1, s[u], s, g)
else:
# 当前节点是偶数节点需要往下递归计算s[j] - s[i]的最小值即为当前偶数节点ap的最小值
p = self.INF
for next in g[u]:
self.dfs(next, depth + 1, 0, s, g)
p = min(p, s[next] - last_s)
if p < 0: self.res = -self.INF
for next in g[u]:
# 累积上当前局部的奇数节点的值
self.res += s[next] - last_s - p
# 累加上偶数节点的值
if p != self.INF: self.res += p
def process(self):
n = int(input())
g = [list() for i in range(n + 10)]
a = list(map(int, input().split()))
for i in range(2, n + 1):
# a[i-2]的子节点为i
g[a[i - 2]].append(i)
# s前面加上一个0元素的下标可以从1开始比较方便处理
s = [0] + list(map(int, input().split()))
# 由于节点1在dfs的时候不会被计算到所以将节点1的权值之和加到答案中
self.res = s[1]
self.dfs(1, 1, 0, s, g)
if self.res < 0: self.res = -1
print(self.res)
if __name__ == '__main__':
sys.setrecursionlimit(10 ** 5)
Solution().process()
go：
package main
import (
"bufio"
"fmt"
"io"
"os"
)
const N, INF = 100010, 10000000000
var (
// 数组模拟邻接表
h, e, ne, s [N]int
res int
idx int
)
// 节点a向节点b连一条有向边
func add(a int, b int) {
e[idx] = b
ne[idx] = h[a]
h[a] = idx
idx += 1
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
func dfs(u int, depth int, last_s int) {
if depth%2 == 1 {
for i := h[u]; i != -1; i = ne[i] {
j := e[i]
dfs(j, depth+1, s[u])
}
} else {
p := INF
for i := h[u]; i != -1; i = ne[i] {
j := e[i]
dfs(j, depth+1, 0)
p = min(p, s[j]-last_s)
}
// p < 0 说明不满足题目的要求
if p < 0 {
res = -INF
}
for i := h[u]; i != -1; i = ne[i] {
j := e[i]
res += s[j] - last_s - p
}
if p != INF {
res += p
}
}
}
func run(r io.Reader, w io.Writer) {
in := bufio.NewReader(r)
out := bufio.NewWriter(w)
// 将缓存数据写入到标准输出中
defer out.Flush()
var n, p int
fmt.Fscan(in, &n)
// 需要将表头初始化为-1
for i := 0; i < n+10; i++ {
h[i] = -1
}
for i := 2; i <= n; i++ {
fmt.Fscan(in, &p)
add(p, i)
}
for i := 1; i <= n; i++ {
fmt.Fscan(in, &s[i])
}
res = s[1]
dfs(1, 1, 0)
if res < 0 {
res = -1
}
fmt.Fprintln(out, res)
}
func main() {
run(os.Stdin, os.Stdout)
}