結果
問題 | No.1221 木 *= 3 |
ユーザー |
|
提出日時 | 2023-05-05 17:45:36 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 427 ms / 2,000 ms |
コード長 | 730 bytes |
コンパイル時間 | 205 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 122,876 KB |
最終ジャッジ日時 | 2024-11-23 02:31:26 |
合計ジャッジ時間 | 8,667 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 18 |
ソースコード
n = int(input())a = list(map(int, input().split()))b = list(map(int, input().split()))g = [[] for _ in range(n)]for _ in range(n - 1):u, v = map(int, input().split())u -= 1v -= 1g[u].append(v)g[v].append(u)dp = [[0 for _ in range(2)] for _ in range(n)]src = 0st = [~ src, src]par = [None for _ in range(n)]while len(st) > 0:cur = st.pop()if cur >= 0:for nxt in g[cur]:if nxt == par[cur]:continuepar[nxt] = curst.append(~ nxt)st.append(nxt)else:dp[~ cur][0] += a[~ cur]if not par[~ cur] is None:dp[par[~ cur]][0] += max(dp[~ cur])dp[par[~ cur]][1] += max(dp[~ cur][0], dp[~ cur][1] + b[~ cur] + b[par[~ cur]])print(max(dp[src]))