結果

問題 No.1221 木 *= 3
ユーザー uni_python
提出日時 2020-09-06 22:51:49
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 638 ms / 2,000 ms
コード長 2,315 bytes
コンパイル時間 161 ms
コンパイル使用メモリ 82,292 KB
実行使用メモリ 117,924 KB
最終ジャッジ日時 2024-11-29 07:46:06
合計ジャッジ時間 10,283 ms
ジャッジサーバーID
(参考情報)
judge2 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import sys
input=sys.stdin.readline
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
"""
&(=j)
+a
-bi*di
-Σbj ←j1
bj
131
DP
max() + ai
max(+bi+bj)
"""
def main():
N=I()
A=LI()
B=LI()
adj=[[]for _ in range(N)]
for _ in range(N-1):
u,v=MI()
u-=1
v-=1
adj[u].append(v)
adj[v].append(u)
import queue
q=queue.Queue()
q.put((0,-1))
D=[0]*N
G=[[]for _ in range(N)] #
while not q.empty():
v,p=q.get()
for nv in adj[v]:
if nv!=p:
G[v].append(nv)
D[nv]=D[v]+1
q.put((nv,v))
L=[]
for i in range(N):
aaa=(D[i],i)
L.append(aaa)
L.sort(reverse=True) #
inf=10**16
dp1=[-inf]*N # ii
dp2=[0]*N # ii
for i in range(N):
v=L[i][1]
# v
temp=A[v]
for nv in G[v]:
temp+=max(dp1[nv], dp2[nv])
dp1[v]=temp
#v
temp=0
for nv in G[v]:
temp+=max(dp1[nv], dp2[nv]+B[v]+B[nv])
dp2[v]=temp
print(max(dp1[0], dp2[0]))
main()
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0