結果
問題 |
No.2618 除霊
|
ユーザー |
![]() |
提出日時 | 2024-01-26 22:50:16 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,123 ms / 2,000 ms |
コード長 | 1,206 bytes |
コンパイル時間 | 429 ms |
コンパイル使用メモリ | 82,688 KB |
実行使用メモリ | 141,212 KB |
最終ジャッジ日時 | 2024-09-28 08:43:53 |
合計ジャッジ時間 | 34,047 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 43 |
ソースコード
n=int(input()) e=[[] for i in range(n)] for i in range(n-1): a,b=map(int,input().split()) a-=1 b-=1 e[a]+=[b] e[b]+=[a] m=int(input()) x=[0]*n y=[0]*n for s in list(map(int,input().split())): x[s-1]+=1 for t in e[s-1]: x[t]+=1 y[s-1]=1 X=0 v=[0]*n u=[0]*n p=[0]*n g=[0]*n q=[0] while len(q)>0: s=q[-1] if v[s]==0: v[s]=1 X+=x[s]>=1 while g[s]<len(e[s]): t=e[s][g[s]] if v[t]==0: break g[s]+=1 if g[s]<len(e[s]): q+=[t] p[t]=s else: for t in e[s]: if t!=p[s]: u[s]+=x[t]==1 q.pop() for i in range(n): a=0 s=i for t in e[s]: if t!=p[s]: if (y[s],y[t])==(0,0): pass if (y[s],y[t])==(0,1): a+=u[t]+(x[t]==1) if (y[s],y[t])==(1,0): a+=(x[t]==1) if (y[s],y[t])==(1,1): a+=u[t]+(x[t]==2) elif s!=0: if (y[s],y[p[s]])==(0,0): pass if (y[s],y[p[s]])==(0,1): a+=u[t]+(x[p[s]]==1)-(x[s]==1) if p[s]!=0: a+=(x[p[p[s]]]==1) if (y[s],y[p[s]])==(1,0): a+=(x[p[s]]==1) if (y[s],y[p[s]])==(1,1): a+=u[p[s]]+(x[p[s]]==2) if p[s]!=0: a+=(x[p[p[s]]]==1) a+=x[s]>0 print(X-a)