Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import sys
- input = sys.stdin.readline
- n, r = map(int, input().split(' '))
- adj = [ [] for i in range(n+1) ]
- vis = [False for i in range(n+1)]
- prev = [-1 for i in range(n+1)]
- bunnies = [-1 for i in range(n+1)]
- for i in range(n-1):
- x, y = list(map(int, input().split(' ')))
- adj[x].append(y)
- adj[y].append(x)
- b = []
- for i in range(r):
- x = int(input())
- b.append(x)
- bunnies[x] = 0
- #while len(b) > 0:
- # node = b.pop(0)
- # for i in range(0, len(adj[node-1])):
- # if bunnies[adj[node-1][i]-1] == False:
- # bunnies[adj[node-1][i]-1] = bunnies[node-1] + 1
- # b.append(bunnies[adj[node-1][i]])
- while len(b) > 0:
- cur = b.pop(0)
- for neighbor in adj[cur]:
- if bunnies[neighbor] == -1:
- bunnies[neighbor] = bunnies[cur] + 1
- b.append(neighbor)
- start, end = list(map(int, input().split(' ')))
- queue = [start]
- vis[start] = True
- while len(queue) > 0:
- node = queue.pop(0)
- for neighbor in adj[node]:
- if vis[neighbor] == False:
- vis[neighbor] = True
- queue.append(neighbor)
- prev[neighbor] = node
- cur, minrab = end, 1000000000
- while cur != -1:
- minrab = min(minrab, bunnies[cur])
- cur = prev[cur]
- print(minrab)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement