結果

問題 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         ←頂点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