fork download
  1. import sys
  2. from collections import defaultdict
  3.  
  4. def Ints(): return map(int, sys.stdin.readline().strip().split())
  5. def Strs(): return map(str, sys.stdin.readline().strip().split())
  6. def Array(): return list(map(int, sys.stdin.readline().strip().split()))
  7. def Str(): return sys.stdin.readline().strip()
  8. def Int(): return int(sys.stdin.readline().strip())
  9. def MOD(): return 1000000007
  10.  
  11. class DFS:
  12. def __init__(self,n):
  13. self.ins = [0 for i in range(n+1)]
  14. self.out = [0 for i in range(n+1)]
  15. self.visited = [False] * (n+1)
  16. self.timer = 0
  17.  
  18. def dfs(self,graph,node):
  19. self.visited[node] = True
  20. self.ins[node] = self.timer
  21. self.timer += 1
  22. for i in graph[node]:
  23. if self.visited[i] == False:
  24. self.dfs(graph,i)
  25. self.out[node] = self.timer
  26. self.timer += 1
  27.  
  28. if __name__ == "__main__":
  29. n,m = Ints()
  30. graph = defaultdict(list)
  31. for _ in range(n-1):
  32. u,v = Ints()
  33. graph[u].append(v)
  34. graph[v].append(u)
  35. d = DFS(n)
  36. d.dfs(graph,1)
  37. for _ in range(m):
  38. ks = Array()
  39. inRoot,outRoot = d.ins[1],d.out[1]
  40. ans = "YES"
  41. for j in range(1,ks[0]+1):
  42. if inRoot > d.ins[ks[j]] or outRoot < d.out[ks[j]]:
  43. ans = "NO"
  44. print(ans)
  45.  
Success #stdin #stdout 0.02s 9248KB
stdin
10 6
1 2
1 3
1 4
2 5
2 6
3 7
7 8
7 9
9 10
4 3 8 9 10
3 2 4 6
3 2 1 5
3 4 8 2
2 6 10
3 5 4 7
stdout
YES
YES
YES
YES
YES
YES