結果
問題 | No.1221 木 *= 3 |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
import sysinput=sys.stdin.readlinedef 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-=1v-=1adj[u].append(v)adj[v].append(u)import queueq=queue.Queue()q.put((0,-1))D=[0]*NG=[[]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]+1q.put((nv,v))L=[]for i in range(N):aaa=(D[i],i)L.append(aaa)L.sort(reverse=True) # 深い順に見るinf=10**16dp1=[-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=0for nv in G[v]:temp+=max(dp1[nv], dp2[nv]+B[v]+B[nv])dp2[v]=tempprint(max(dp1[0], dp2[0]))main()