結果
問題 |
No.3222 Let the World Forget Me
|
ユーザー |
![]() |
提出日時 | 2025-08-07 02:42:01 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 475 ms / 2,000 ms |
コード長 | 955 bytes |
コンパイル時間 | 377 ms |
コンパイル使用メモリ | 82,388 KB |
実行使用メモリ | 115,232 KB |
最終ジャッジ日時 | 2025-08-07 02:42:14 |
合計ジャッジ時間 | 11,304 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 31 |
ソースコード
import sys input = sys.stdin.readline from collections import deque from operator import itemgetter from heapq import heappop,heappush N,M=map(int,input().split()) P=list(map(int,input().split())) E=[set() for i in range(N)] for i in range(N-1): a,b=map(int,input().split()) a-=1 b-=1 E[a].add(b) E[b].add(a) DIS=[1<<60]*N Q=deque() C=list(map(int,input().split())) for c in C: c-=1 Q.append(c) DIS[c]=0 while Q: x=Q.popleft() for to in E[x]: if DIS[to]>DIS[x]+1: DIS[to]=DIS[x]+1 Q.append(to) CQ=[] for i in range(N): if len(E[i])==1: CQ.append((-P[i],DIS[i],i)) CQ.sort() now=0 ANS=0 while CQ: p,d,ind=heappop(CQ) if d<=now: continue else: ANS-=p now+=1 to=list(E[ind])[0] E[ind].remove(to) E[to].remove(ind) if len(E[to])==1: heappush(CQ,(-P[to],DIS[to],to)) print(ANS)