結果
問題 | No.1221 木 *= 3 |
ユーザー |
![]() |
提出日時 | 2020-09-05 02:04:44 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 291 ms / 2,000 ms |
コード長 | 939 bytes |
コンパイル時間 | 332 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 134,332 KB |
最終ジャッジ日時 | 2024-11-26 21:36:38 |
合計ジャッジ時間 | 6,045 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 18 |
ソースコード
import sysread = sys.stdin.buffer.readreadline = sys.stdin.buffer.readlinereadlines = sys.stdin.buffer.readlinesn = int(readline())a = [0] + list(map(int,readline().split()))b = [0] + list(map(int,readline().split()))if(n==1):print(max(0,a[1]))exit()data = list(map(int,read().split()))links = [[] for _ in range(n+1)]it = iter(data)for u,v in zip(it,it):links[u].append(v)links[v].append(u)stack = [1]done = [0] * (n+1)done[1] = 1tp = []child = [[] for _ in range(n+1)]while(stack):i = stack.pop()tp.append(i)for j in links[i]:if(done[j] == 1):continuedone[j] = 1child[i].append(j)stack.append(j)scores = [[0,0] for _ in range(n+1)]for i in tp[::-1]:for j in child[i]:scores[i][0] += max(scores[j][0] + b[i] + b[j], scores[j][1])scores[i][1] += max(scores[j])scores[i][1] += a[i]print(max(scores[1]))