結果
問題 | No.1221 木 *= 3 |
ユーザー |
![]() |
提出日時 | 2020-09-05 05:17:46 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 685 ms / 2,000 ms |
コード長 | 981 bytes |
コンパイル時間 | 126 ms |
コンパイル使用メモリ | 12,800 KB |
実行使用メモリ | 48,492 KB |
最終ジャッジ日時 | 2024-11-27 08:30:22 |
合計ジャッジ時間 | 11,294 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 18 |
ソースコード
import sysinput = sys.stdin.readlineN=int(input())A=[0]+list(map(int,input().split()))B=[0]+list(map(int,input().split()))E=[[] for i in range(N+1)]for i in range(N-1):x,y=map(int,input().split())E[x].append(y)E[y].append(x)QUE=[1]Parent=[-1]*(N+1)Parent[1]=N+1TOP_SORT=[] # トポロジカルソートwhile QUE:x=QUE.pop()TOP_SORT.append(x)for to in E[x]:if Parent[to]==-1:Parent[to]=xQUE.append(to)DP0=[-1<<100]*(N+1)DP1=[-1<<100]*(N+1)for x in TOP_SORT[::-1]:if x!=1 and len(E[x])==1:DP0[x]=A[x]DP1[x]=0else:S=0for to in E[x]:if to==Parent[x]:continueS+=max(DP0[to],DP1[to])DP0[x]=S+A[x]S2=0for to in E[x]:if to==Parent[x]:continueS2+=max(DP1[to]+B[x]+B[to],DP0[to])DP1[x]=S2print(max(DP0[1],DP1[1]))