結果

問題 No.2618 除霊
ユーザー とりゐとりゐ
提出日時 2024-01-26 22:47:36
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,025 ms / 2,000 ms
コード長 895 bytes
コンパイル時間 575 ms
コンパイル使用メモリ 81,700 KB
実行使用メモリ 184,856 KB
最終ジャッジ日時 2024-01-26 22:48:18
合計ジャッジ時間 34,482 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 36 ms
53,460 KB
testcase_01 AC 37 ms
53,460 KB
testcase_02 AC 33 ms
53,460 KB
testcase_03 AC 33 ms
53,460 KB
testcase_04 AC 33 ms
53,460 KB
testcase_05 AC 34 ms
53,460 KB
testcase_06 AC 844 ms
123,880 KB
testcase_07 AC 841 ms
123,096 KB
testcase_08 AC 947 ms
142,000 KB
testcase_09 AC 917 ms
143,180 KB
testcase_10 AC 813 ms
146,668 KB
testcase_11 AC 718 ms
118,096 KB
testcase_12 AC 891 ms
141,284 KB
testcase_13 AC 571 ms
119,304 KB
testcase_14 AC 955 ms
184,856 KB
testcase_15 AC 515 ms
113,940 KB
testcase_16 AC 563 ms
114,732 KB
testcase_17 AC 765 ms
137,780 KB
testcase_18 AC 918 ms
163,308 KB
testcase_19 AC 587 ms
115,912 KB
testcase_20 AC 541 ms
114,156 KB
testcase_21 AC 772 ms
135,652 KB
testcase_22 AC 896 ms
171,964 KB
testcase_23 AC 686 ms
121,244 KB
testcase_24 AC 654 ms
121,052 KB
testcase_25 AC 892 ms
146,424 KB
testcase_26 AC 994 ms
164,748 KB
testcase_27 AC 688 ms
120,648 KB
testcase_28 AC 676 ms
120,716 KB
testcase_29 AC 933 ms
147,084 KB
testcase_30 AC 1,025 ms
179,176 KB
testcase_31 AC 1,006 ms
142,320 KB
testcase_32 AC 543 ms
110,820 KB
testcase_33 AC 686 ms
115,608 KB
testcase_34 AC 693 ms
120,212 KB
testcase_35 AC 832 ms
125,840 KB
testcase_36 AC 900 ms
136,556 KB
testcase_37 AC 864 ms
137,768 KB
testcase_38 AC 928 ms
144,812 KB
testcase_39 AC 966 ms
148,732 KB
testcase_40 AC 908 ms
147,752 KB
testcase_41 AC 908 ms
147,216 KB
testcase_42 AC 783 ms
146,204 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

from sys import stdin
input=lambda :stdin.readline()[:-1]

n=int(input())
edge=[[] for i in range(n)]
for _ in range(n-1):
  a,b=map(lambda x:int(x)-1,input().split())
  edge[a].append(b)
  edge[b].append(a)

m=int(input())
a=list(map(lambda x:int(x)-1,input().split()))
b=[0]*n
for i in a:
  b[i]=1

d={}
mem=[0]*n
ans=0
for v in range(n):
  res=[]
  for u in edge[v]:
    if b[u]:
      res.append(u)
  if b[v]:
    res.append(v)
  if len(res)<=2:
    res.sort()
    res=tuple(res)
    if res not in d:
      d[res]=0
    d[res]+=1
  if len(res)>=1:
    ans+=1
  mem[v]=res

for v in range(n):
  ansv=ans
  if tuple([v]) in d:
    ansv-=d[tuple([v])]
  for u in edge[v]:
    if tuple([u]) in d:
      ansv-=d[tuple([u])]
    x=[u,v]
    x.sort()
    if tuple(x) in d:
      ansv-=d[tuple(x)]
  if len(mem[v])>=3:
    ansv-=1
  elif len(mem[v])==2 and v not in mem[v]:
    ansv-=1
  print(ansv)
0