blob: 08c10b2451f1853a48b07aafc796e9700da6cdce (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
from queue import Queue
N, M = tuple(map(int,input().split()))
pho_restaurants = tuple(map(int,input().split()))
tree = dict()
for i in range(N-1):
a,b = tuple(map(int,input().split()))
if a in tree:
tree[a].add(b)
else:
tree[a] = {b}
if b in tree:
tree[b].add(a)
else:
tree[b] = {a}
q = Queue()
for i in pho_restaurants:
q.put((i, 0, 0))
seen = set()
complete = (10 ** len(pho_restaurants) - 1)/9
while not q.empty():
current, length, pho_seen = q.get()
if (current, pho_seen) in seen:
continue
else:
seen.add((current,pho_seen))
if current in pho_restaurants:
if (pho_seen // (10 ** pho_restaurants.index(current))) % 10 == 0:
pho_seen += 10 ** pho_restaurants.index(current)
if pho_seen == complete:
print(length)
break
for r in tree[current]:
q.put((r, length + 1, pho_seen))
|
