結果
問題 |
No.2618 除霊
|
ユーザー |
![]() |
提出日時 | 2024-01-29 01:32:47 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,037 bytes |
コンパイル時間 | 374 ms |
コンパイル使用メモリ | 81,920 KB |
実行使用メモリ | 424,868 KB |
最終ジャッジ日時 | 2024-09-28 09:59:08 |
合計ジャッジ時間 | 14,470 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 14 TLE * 1 -- * 28 |
ソースコード
import sys input = sys.stdin.readline N=int(input()) 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) ANS=[0]*N M=int(input()) V=list(map(int,input().split())) for i in range(M): V[i]-=1 BLIST=[0]*N for v in V: BLIST[v]=1 for v in V: ANS[v]+=1 for to in E[v]: ANS[to]+=1 SUM=0 for a in ANS: if a>=1: SUM+=1 def neighbor(A): if len(A)==0: return set() S=E[A[0]]|{A[0]} for i in range(1,len(A)): S=S&(E[A[i]]|{A[i]}) return S ANSLIST=[SUM]*N DICT=dict() for i in range(N): LIST=[] if BLIST[i]==1: LIST.append(i) for to in E[i]: if BLIST[to]==1: LIST.append(to) LIST.sort() if tuple(LIST) in DICT: DICT[tuple(LIST)].append(i) else: DICT[tuple(LIST)]=[i] for d in DICT: S=neighbor(d) #print(d,S,DICT[d]) for a in S: ANSLIST[a]-=len(DICT[d]) print("\n".join(map(str,ANSLIST)))