結果

問題 No.1221 木 *= 3
ユーザー uni_pythonuni_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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 70 ms
67,328 KB
testcase_01 AC 64 ms
67,200 KB
testcase_02 AC 64 ms
67,328 KB
testcase_03 AC 66 ms
67,328 KB
testcase_04 AC 63 ms
66,816 KB
testcase_05 AC 64 ms
67,328 KB
testcase_06 AC 65 ms
67,200 KB
testcase_07 AC 609 ms
117,628 KB
testcase_08 AC 606 ms
117,548 KB
testcase_09 AC 638 ms
117,924 KB
testcase_10 AC 628 ms
117,776 KB
testcase_11 AC 632 ms
117,832 KB
testcase_12 AC 357 ms
116,676 KB
testcase_13 AC 359 ms
116,956 KB
testcase_14 AC 369 ms
117,000 KB
testcase_15 AC 370 ms
116,800 KB
testcase_16 AC 368 ms
116,752 KB
testcase_17 AC 589 ms
115,764 KB
testcase_18 AC 587 ms
116,052 KB
testcase_19 AC 600 ms
115,596 KB
testcase_20 AC 608 ms
115,804 KB
testcase_21 AC 595 ms
115,764 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