Submission #74771537

---

Source Code Expand

import sys


def solve(rev_p, w):
    order = []
    stack = [0]
    while stack:
        v = stack.pop()
        order.append(v)
        for nv in rev_p[v]:
            stack.append(nv)

    sum_dp = [0] * len(rev_p)
    diff_dp = [0] * len(rev_p)
    for v in reversed(order):
        if len(rev_p[v]) == 0:
            sum_dp[v] = w[v]
            diff_dp[v] = 0
            continue

        child_sums = [sum_dp[nv] for nv in rev_p[v]]
        child_diffs = [diff_dp[nv] for nv in rev_p[v]]
        sum_dp[v] = sum(child_sums)
        diff_dp[v] = max(max(child_diffs), max(child_sums) - min(child_sums))

    return diff_dp[0]


data = list(map(int, sys.stdin.buffer.read().split()))
ptr = 0

n = data[ptr]
ptr += 1
rev_p = [[] for _ in range(n)]
p = data[ptr:ptr + n - 1]
ptr += n - 1
w = data[ptr:ptr + n]
for i in range(n - 1):
    rev_p[p[i] - 1].append(i + 1)
print(solve(rev_p, w))

Submission Info

Judge Result