Escape The Maze (easy version) (Codeforces 1611E1)
Tags: Greedy, shortest paths

The only difference with E2 is the question of the problem..Vlad built a maze out of $$$n$$$ rooms and $$$n-1$$$ bidirectional corridors. From any room $$$u$$$ any other room $$$v$$$ can be reached through a sequence of corridors. Thus, the room system forms an undirected tree.Vlad invited $$$k$$$ friends to play a game with them.Vlad starts the game in the room $$$1$$$ and wins if he reaches a room other than $$$1$$$, into which exactly one corridor leads.Friends are placed in the maze: the friend with number $$$i$$$ is in the room $$$x_i$$$, and no two friends are in the same room (that is, $$$x_i \neq x_j$$$ for all $$$i \neq j$$$). Friends win if one of them meets Vlad in any room or corridor before he wins.For one unit of time, each participant of the game can go through one corridor. All participants move at the same time. Participants may not move. Each room can fit all participants at the same time. Friends know the plan of a maze and intend to win. Vlad is a bit afraid of their ardor. Determine if he can guarantee victory (i.e. can he win in any way friends play).In other words, determine if there is such a sequence of Vlad's moves that lets Vlad win in any way friends play.

Input: The first line of the input contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases in the input. The input contains an empty string before each test case.The first line of the test case contains two numbers $$$n$$$ and $$$k$$$ ($$$1 \le k < n \le 2\cdot 10^5$$$) — the number of rooms and friends, respectively.The next line of the test case contains $$$k$$$ integers $$$x_1, x_2, \dots, x_k$$$ ($$$2 \le x_i \le n$$$) — numbers of rooms with friends. All $$$x_i$$$ are different.The next $$$n-1$$$ lines contain descriptions of the corridors, two numbers per line $$$v_j$$$ and $$$u_j$$$ ($$$1 \le u_j, v_j \le n$$$) — numbers of rooms that connect the $$$j$$$ corridor. All corridors are bidirectional. From any room, you can go to any other by moving along the corridors.It is guaranteed that the sum of the values $$$n$$$ over all test cases in the test is not greater than $$$2\cdot10^5$$$.

Output: Print $$$t$$$ lines, each line containing the answer to the corresponding test case. The answer to a test case should be "YES" if Vlad can guarantee himself a victory and "NO" otherwise.You may print every letter in any case you want (so, for example, the strings "yEs", "yes", "Yes" and "YES" will all be recognized as positive answers).

Note: In the first test case, regardless of the strategy of his friends, Vlad can win by going to room $$$4$$$. The game may look like this:  The original locations of Vlad and friends. Vlad is marked in green, friends — in red.   Locations after one unit of time.   End of the game. Note that if Vlad tries to reach the exit at the room $$$8$$$, then a friend from the $$$3$$$ room will be able to catch him.

Sample Inputs:
4

8 2
5 3
4 7
2 5
1 6
3 6
7 2
1 7
6 8

3 1
2
1 2
2 3

3 1
2
1 2
1 3

3 2
2 3
3 1
1 2

Sample Outputs:
YES
NO
YES
NO

Solution (Python):
import io
import os
import collections
import math
import functools
import itertools
import bisect
import heapq
from sys import stdin, stdout, stderr, setrecursionlimit
from collections import *
from math import *
from functools import *
from itertools import *
from heapq import *
from bisect import bisect_left, bisect_right, insort_left, insort_right
setrecursionlimit(1000000)
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def get_ints():
    return list(map(int, input().split()))

def get_int():
    return int(input())

def get_str():
    return ''.join(list(map(chr, input().rstrip())))

def eprint(*args):
    stderr.write(', '.join(map(str, args)) + '\n')

def print(*args):
    stdout.write(' '.join(map(str, args)) + '\n')

def solve():
    input()
    (n, k) = get_ints()
    friends = get_ints()
    graph = [[] for _ in range(n + 1)]
    for _ in range(n - 1):
        (u, v) = get_ints()
        graph[u].append(v)
        graph[v].append(u)
    visited = [False] * (n + 1)
    visited[1] = True
    eliminated = [False] * (n + 1)
    fpos = set()
    for x in friends:
        eliminated[x] = True

    def is_end(u):
        return u != 1 and len(graph[u]) == 1
    vtodo = [1]
    ftodo = friends[:]
    while vtodo:
        nftodo = []
        nvtodo = []
        for u in ftodo:
            for v in graph[u]:
                if not eliminated[v]:
                    nftodo.append(v)
                    eliminated[v] = True
        for u in vtodo:
            if is_end(u):
                return 'YES'
            for v in graph[u]:
                if not eliminated[v] and (not visited[v]):
                    nvtodo.append(v)
                    visited[v] = True
        ftodo = nftodo
        vtodo = nvtodo
    return 'NO'
T = get_int()
for _ in range(T):
    print(solve())

Solution (Python):
from collections import deque
from sys import stdin, gettrace

class Stree:

    def __init__(self, f, n, default, init_data):
        self.ln = 2 ** (n - 1).bit_length()
        self.data = [default] * (self.ln * 2)
        self.f = f
        for (i, d) in enumerate(init_data):
            self.data[self.ln + i] = d
        for j in range(self.ln - 1, -1, -1):
            self.data[j] = f(self.data[j * 2], self.data[j * 2 + 1])

    def update(self, i, a):
        p = self.ln + i
        self.data[p] = a
        while p > 1:
            p = p // 2
            self.data[p] = self.f(self.data[p * 2], self.data[p * 2 + 1])

    def get(self, i, j):

        def _get(l, r, p):
            if i <= l and j >= r:
                return self.data[p]
            else:
                m = (l + r) // 2
                if j <= m:
                    return _get(l, m, p * 2)
                elif i >= m:
                    return _get(m, r, p * 2 + 1)
                else:
                    return self.f(_get(l, m, p * 2), _get(m, r, p * 2 + 1))
        return _get(0, self.ln, 1)
if gettrace():

    def inputi():
        return input()
else:

    def input():
        return next(stdin)[:-1]

    def inputi():
        return stdin.buffer.readline()

def readGraph(n, m):
    adj = [[] for _ in range(n)]
    for _ in range(m):
        (u, v) = map(int, input().split())
        adj[u - 1].append(v - 1)
        adj[v - 1].append(u - 1)
    return adj

def readTree(n):
    return readGraph(n, n - 1)

def solve():
    input()
    (n, k) = map(int, input().split())
    xx = {int(a) - 1 for a in input().split()}
    if 0 in xx:
        print('NO')
    adj = readTree(n)
    q = deque()
    parent = [-1] * n
    q.append(0)
    while q:
        v = q.popleft()
        for a in adj[v]:
            if a != 0 and a != parent[v]:
                parent[a] = v
                q.append(a)
    vp = {0}
    visited = xx.copy()
    while vp:
        if any((v != 0 and len(adj[v]) == 1 for v in vp)):
            print('YES')
            return
        vp = {w for v in vp for w in adj[v] if w != parent[v]}
        vp -= xx
        xx = {parent[x] for x in xx if parent[x] != -1}
        xx -= visited
        visited |= xx
        vp -= xx
    print('NO')

def main():
    t = int(input())
    for _ in range(t):
        solve()
if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
from sys import stdin, gettrace

class Stree:

    def __init__(self, f, n, default, init_data):
        self.ln = 2 ** (n - 1).bit_length()
        self.data = [default] * (self.ln * 2)
        self.f = f
        for (i, d) in enumerate(init_data):
            self.data[self.ln + i] = d
        for j in range(self.ln - 1, -1, -1):
            self.data[j] = f(self.data[j * 2], self.data[j * 2 + 1])

    def update(self, i, a):
        p = self.ln + i
        self.data[p] = a
        while p > 1:
            p = p // 2
            self.data[p] = self.f(self.data[p * 2], self.data[p * 2 + 1])

    def get(self, i, j):

        def _get(l, r, p):
            if i <= l and j >= r:
                return self.data[p]
            else:
                m = (l + r) // 2
                if j <= m:
                    return _get(l, m, p * 2)
                elif i >= m:
                    return _get(m, r, p * 2 + 1)
                else:
                    return self.f(_get(l, m, p * 2), _get(m, r, p * 2 + 1))
        return _get(0, self.ln, 1)
if gettrace():

    def inputi():
        return input()
else:

    def input():
        return next(stdin)[:-1]

    def inputi():
        return stdin.buffer.readline()

def readGraph(n, m):
    adj = [[] for _ in range(n)]
    for _ in range(m):
        (u, v) = map(int, input().split())
        adj[u - 1].append(v - 1)
        adj[v - 1].append(u - 1)
    return adj

def readTree(n):
    return readGraph(n, n - 1)

def solve():
    input()
    (n, k) = map(int, input().split())
    xx = {int(a) - 1 for a in input().split()}
    if 0 in xx:
        print('NO')
    adj = readTree(n)
    q = deque()
    parent = [-1] * n
    q.append(0)
    while q:
        v = q.popleft()
        for a in adj[v]:
            if a != 0 and a != parent[v]:
                parent[a] = v
                q.append(a)
    vp = {0}
    visited = xx.copy()
    while vp:
        if any((v != 0 and len(adj[v]) == 1 for v in vp)):
            print('YES')
            return
        vp = {w for v in vp for w in adj[v] if w != parent[v]}
        vp -= xx
        xx = {parent[x] for x in xx if parent[x] != -1}
        xx -= visited
        visited |= xx
        vp -= xx
    print('NO')

def main():
    t = int(input())
    for _ in range(t):
        solve()
if __name__ == '__main__':
    main()