結果
問題 | No.1221 木 *= 3 |
ユーザー |
![]() |
提出日時 | 2020-09-05 15:10:09 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
RE
|
実行時間 | - |
コード長 | 2,208 bytes |
コンパイル時間 | 304 ms |
コンパイル使用メモリ | 12,800 KB |
実行使用メモリ | 55,084 KB |
最終ジャッジ日時 | 2024-11-28 16:01:26 |
合計ジャッジ時間 | 14,435 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 13 RE * 5 |
ソースコード
import sysimport mathimport collectionsimport bisectimport itertoolsimport decimalimport copyfrom math import log2# import numpy as np# sys.setrecursionlimit(10 ** 6)INF = 10 ** 20# MOD = 10 ** 9 + 7# MOD = 998244353ni = lambda: int(sys.stdin.readline().rstrip())ns = lambda: map(int, sys.stdin.readline().rstrip().split())na = lambda: list(map(int, sys.stdin.readline().rstrip().split()))na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))# ===CODE===def main():n = ni()a = na()b = na()e = [[] for _ in range(n)]for _ in range(n - 1):u, v = na1()e[u].append(v)e[v].append(u)# dp[v][x]:Node vを頂点とした部分木の条件xのとしたときの最大値# x=0:Node vからみて、自分は使用、親ノードは使用としたとき# x=1:Node vからみて、自分は使用、親ノードは削除としたとき# x=2:Node vからみて、自分は削除、親ノードは使用としたとき# x=3:Node vからみて、自分は削除、親ノードは削除としたとき 実装して見返すと3は2と同じ動きなので統合できるなあdp = [[0 for _ in range(4)] for __ in range(n)]def dfs(node, parent):dp[node][0] = b[node] # nodeの親は使う確定のため node==0のときにb[node]足すのはおかしいけど、答えに使わないからOKdp[node][1] = 0 # まぁいらんけど・・・dp[node][2] = a[node] # nodeは使わないの確定なため & nodeの親は使う確定なのでdp[node][3] = a[node] # nodeは使わないの確定なためfor ei in e[node]:if ei != parent:dfs(ei, node)dp[node][0] += max(dp[ei][0] + b[node], dp[ei][2])dp[node][1] += max(dp[ei][0] + b[node], dp[ei][2])dp[node][2] += max(dp[ei][1], dp[ei][3])dp[node][3] += max(dp[ei][1], dp[ei][3])dfs(0, 0)# Node 0の親は存在しないので、親が存在しない1と3が解の候補となるans = max(dp[0][1], dp[0][3])print(ans)if __name__ == '__main__':main()