結果
問題 | No.1221 木 *= 3 |
ユーザー |
👑 ![]() |
提出日時 | 2020-09-04 22:07:51 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 712 ms / 2,000 ms |
コード長 | 1,030 bytes |
コンパイル時間 | 237 ms |
コンパイル使用メモリ | 12,672 KB |
実行使用メモリ | 61,772 KB |
最終ジャッジ日時 | 2024-11-26 12:57:39 |
合計ジャッジ時間 | 10,817 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 18 |
ソースコード
"""タイトルが意味深普通の木dpを考えてみるdp[v][state] = 頂点vを消すかどうかのflagがstateの時の部分木における最大スコア消すと決めた場合、大きいほうをガンガンもらえばいい消さない場合も貪欲にスコアの大きいほうを貰えばいい(消えない場合は自分によって増えるのも加味)"""from sys import stdinimport syssys.setrecursionlimit(300000)def dfs(v,p):ret = [a[v],0]for nex in lis[v]:if nex != p:cat = dfs(nex,v)#消す場合ret[0] += max(cat)#消さない場合ret[1] += max(cat[0] , cat[1] + b[nex] + b[v])return retN = int(stdin.readline())a = list(map(int,stdin.readline().split()))b = list(map(int,stdin.readline().split()))lis = [ [] for i in range(N) ]for i in range(N-1):u,v = map(int,stdin.readline().split())u -= 1v -= 1lis[u].append(v)lis[v].append(u)print( max(dfs(0,0) ))