結果

問題 No.1221 木 *= 3
ユーザー LyricalMaestro
提出日時 2025-08-16 02:13:01
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 351 ms / 2,000 ms
コード長 1,419 bytes
コンパイル時間 232 ms
コンパイル使用メモリ 82,636 KB
実行使用メモリ 108,076 KB
最終ジャッジ日時 2025-08-16 02:13:09
合計ジャッジ時間 7,711 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge6
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

# https://yukicoder.me/problems/no/1221

from collections import deque

MIN_VALUE = -10 ** 18

def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    next_nodes = [[ ] for _ in range(N)]
    for _ in range(N - 1):
        u, v = map(int, input().split())
        next_nodes[u - 1].append(v - 1)
        next_nodes[v - 1].append(u - 1)

    stack = deque()
    parents = [-2] * N
    parents[0] = -1
    stack.append((0, 0))

    # [その頂点を消した時, その頂点を消さなかった時]
    dp = [[MIN_VALUE, MIN_VALUE] for _ in range(N)]

    while len(stack) > 0:
        v, index = stack.pop()

        while index < len(next_nodes[v]):
            w = next_nodes[v][index]
            if w == parents[v]:
                index += 1
                continue

            parents[w] = v
            stack.append((v, index + 1))
            stack.append((w, 0))
            break

        if index == len(next_nodes[v]):
            # dp[v][0]を求める
            ans0 = A[v]
            ans1 = 0
            for w in next_nodes[v]:
                if parents[v] == w:
                    continue

                ans0 += max(dp[w][0], dp[w][1])
                ans1 += max(dp[w][0], dp[w][1] + B[w] + B[v])
            dp[v][0] = ans0
            dp[v][1] = ans1

    
    print(max(dp[0]))



    


if __name__ == "__main__":
    main()
0