[C++知识库]E1 - Escape The Maze (easy version)（双向广搜）

有一个无向图，Vlad和他的k个朋友分别在不同的房间，Vlad在一号房

如果Vlad走到一个只有一条通道的房间，他就获胜

如果他的朋友在途中遇到他，则朋友获胜

每个单位时间，每人可以移动一个单位距离。

解法：双向广搜

初始队列：每个被朋友占领的节点+Vlad所在的节点

遍历队列，如果这个节点没有被占领过，相邻的节点优先占领

// Problem: E1. Escape The Maze (easy version)
// Contest: Codeforces - Codeforces Round #756 (Div. 3)
// URL: https://codeforces.com/problemset/problem/1611/E1
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h> 
using namespace std;
#define ff first
#define ss second
#define lowbit(x) (x&-x)
#define pf(a) printf("%d\n",a)
#define mem(x,y) memset(x,y,sizeof(x))
#define dbg(x) cout << #x << " = " << x << endl
#define rep(i,l,r) for(int i = l; i <= r; i++)
#define fep(i,a,b) for(int i=b; i>=a; --i)
#define PII pair<int,int>
//#define long long in 
typedef long long ll;

const int N = 2e5+10;

int n,k;
int color[N];
vector<int> G[N];

void solve()
{
	scanf("%d %d",&n, &k);
	
	rep(i,1,n) {
		G[i].clear();
		color[i] = -1;
	}
	
	deque<int> q;
	
	rep(i,1,k) {
		int v;
		scanf("%d",&v);
		q.push_back(v);
		color[v] = 0;
	}
	color[1] = 1;
	q.push_back(1);
	rep(i,1,n-1) {
		int u, v;
		scanf("%d %d",&u, &v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	
	while(q.size())
	{
		int u = q.front();
		q.pop_front();
		for(int v : G[u])
		{
			if(color[v]==-1){
				color[v] = color[u];
				q.push_back(v);
			}
		}
	}
	rep(i,2,n) {
		if(G[i].size()==1 && color[i]==1) {
			puts("YES");
			return;
		}
	}
	puts("NO");
	
}

int main()
{
	int t;
	scanf("%d", &t);
	while(t--)
		solve();
	return 0;
}