結果
問題 | No.1221 木 *= 3 |
ユーザー |
![]() |
提出日時 | 2023-02-23 23:47:56 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 249 ms / 2,000 ms |
コード長 | 1,061 bytes |
コンパイル時間 | 314 ms |
コンパイル使用メモリ | 82,428 KB |
実行使用メモリ | 107,928 KB |
最終ジャッジ日時 | 2024-07-23 16:49:17 |
合計ジャッジ時間 | 6,383 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 18 |
ソースコード
import sysreadline = sys.stdin.readlinedef non_rec_dfs(s):stack = []stack.append(~s)stack.append(s)par = [-1] * Ndp0 = [0] * Ndp1 = [0] * Nwhile stack:u = stack.pop()if u >= 0:stack.append(~u)flag = 1for v in G[u]:if v == par[u]:continuepar[v] = ustack.append(v)flag = 0else:u = ~uif par[u] == -1:continuep = par[u]dp0[p] = max(dp0[p] + dp0[u] + A[u], dp0[p] + dp1[u])dp1[p] = max(dp1[p] + dp0[u] + A[u], dp1[p] + dp1[u] + B[u] + B[p])# print(dp0)# print(dp1)return max(dp0[0] + A[0], dp1[0])N = int(readline())A = list(map(int, readline().split()))B = list(map(int, readline().split()))G = [[] for i in range(N)]for i in range(N - 1):u, v = map(int, readline().split())u, v = u - 1, v - 1G[u].append(v)G[v].append(u)print(non_rec_dfs(0))