結果

問題 No.1221 木 *= 3
ユーザー uni_pythonuni_python
提出日時 2020-09-06 22:51:49
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 634 ms / 2,000 ms
コード長 2,315 bytes
コンパイル時間 168 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 117,972 KB
最終ジャッジ日時 2024-05-06 21:35:57
合計ジャッジ時間 9,732 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 75 ms
66,944 KB
testcase_01 AC 77 ms
67,072 KB
testcase_02 AC 70 ms
66,944 KB
testcase_03 AC 71 ms
67,328 KB
testcase_04 AC 70 ms
67,200 KB
testcase_05 AC 72 ms
67,072 KB
testcase_06 AC 71 ms
67,584 KB
testcase_07 AC 609 ms
117,380 KB
testcase_08 AC 607 ms
117,972 KB
testcase_09 AC 625 ms
117,796 KB
testcase_10 AC 634 ms
117,780 KB
testcase_11 AC 615 ms
117,772 KB
testcase_12 AC 351 ms
116,692 KB
testcase_13 AC 350 ms
116,932 KB
testcase_14 AC 360 ms
116,752 KB
testcase_15 AC 358 ms
116,996 KB
testcase_16 AC 353 ms
116,820 KB
testcase_17 AC 568 ms
115,700 KB
testcase_18 AC 541 ms
115,788 KB
testcase_19 AC 562 ms
115,912 KB
testcase_20 AC 565 ms
115,612 KB
testcase_21 AC 572 ms
115,672 KB
権限があれば一括ダウンロードができます

ソースコード

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         ←頂点jの次数が1減る分

なんだけど，bjが存在するかどうかでこの影響値が変わるのかぁ．
例1を見て，頂点3だけ見れば消さない方がいいんだけど，頂点1がもし消えていれば消した方が良い．
これを考慮する必要があるので，結局影響が波及してしまう

木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 # iが頂点となる部分木において，iがない場合の最大値
    dp2=[0]*N    # iが頂点となる部分木において，iがある場合の最大値
    
    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()
0