結果

問題 No.1221 木 *= 3
ユーザー lam6er
提出日時 2025-03-26 15:54:39
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 442 ms / 2,000 ms
コード長 1,915 bytes
コンパイル時間 291 ms
コンパイル使用メモリ 82,380 KB
実行使用メモリ 138,104 KB
最終ジャッジ日時 2025-03-26 15:55:59
合計ジャッジ時間 8,346 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from sys import stdin
sys.setrecursionlimit(1 << 25)

def main():
    N = int(stdin.readline())
    a = list(map(int, stdin.readline().split()))
    b = list(map(int, stdin.readline().split()))
    edges = [[] for _ in range(N+1)]
    for _ in range(N-1):
        u, v = map(int, stdin.readline().split())
        edges[u].append(v)
        edges[v].append(u)
    
    root = 1
    parent = [0] * (N + 1)
    children = [[] for _ in range(N + 1)]
    stack = [(root, 0)]
    while stack:
        u, p = stack.pop()
        parent[u] = p
        for v in edges[u]:
            if v != p:
                children[u].append(v)
                stack.append((v, u))
    
    max_score = [[-1e18] * 2 for _ in range(N + 1)]
    
    post_stack = []
    visited = [False] * (N + 1)
    post_order = []
    stack = [(root, False)]
    while stack:
        u, done = stack.pop()
        if done:
            post_order.append(u)
            continue
        visited[u] = True
        stack.append((u, True))
        for v in reversed(children[u]):
            stack.append((v, False))
    
    for u in post_order:
        sum_child_0 = 0
        sum_child_1 = 0
        for v in children[u]:
            sum_child_0 += max_score[v][0]
            sum_child_1 += max_score[v][1]
        
        score0_p0 = sum_child_0
        score1_p0 = -a[u-1] + sum_child_1
        max0 = max(score0_p0, score1_p0)
        
        if parent[u] == 0:
            score0_p1 = 0
            score1_p1 = 0
        else:
            score0_p1 = sum_child_0
            score1_p1 = -a[u-1] + (b[u-1] + b[parent[u]-1]) + sum_child_1
        max1 = max(score0_p1, score1_p1) if parent[u] != 0 else max0
        
        max_score[u][0] = max0
        max_score[u][1] = max1 if parent[u] != 0 else max_score[u][1]
    
    total_a = sum(a)
    ans = total_a + max_score[root][0]
    print(ans)

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