与E2唯一的区别是问题的问题..
Vlad 用 $$$n$$$ 个房间和 $$$n-1$$$ 双向走廊建造了一个迷宫。从任何房间 $$$u$$$ 到任何其他房间 $$$v$$$ 都可以通过一系列走廊到达。这样,房间系统就形成了一棵无向树。
Vlad 邀请 $$$k$$$ 朋友和他们一起玩游戏。
Vlad 在 $$$1$$$ 房间开始游戏,如果他到达 $$$1$$$ 以外的房间(恰好有一条走廊通向该房间),则获胜。
朋友被放置在迷宫中:编号为 $$$i$$$ 的朋友在房间 $$$x_i$$$ 中,并且没有两个朋友在同一个房间中(即,对于所有 $$$i \neq j$$$,$$$x_i \neq x_j$$$)。如果朋友中的一个人在弗拉德获胜之前在任何房间或走廊遇到他,那么他就获胜。
在一个单位时间内,每个游戏参与者可以通过一条走廊。所有参与者同时移动。参与者不得移动。每个房间可同时容纳所有参与者。
朋友们知道迷宫的设计并打算获胜。弗拉德有点害怕他们的热情。确定他是否能保证胜利(即他能以朋友玩的任何方式获胜)。
换句话说,确定是否存在这样一个 Vlad 的动作序列,可以让 Vlad 以任何朋友的玩法获胜。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 输入中测试用例的数量。输入在每个测试用例之前包含一个空字符串。
测试用例的第一行包含两个数字 $$$n$$$ 和 $$$k$$$ ($$$1 \le k < n \le 2\cdot 10^5$$$) — 分别是房间和朋友的数量。
测试用例的下一行包含 $$$k$$$ 整数 $$$x_1, x_2, \dots, x_k$$$ ($$$2 \le x_i \le n$$$) — 有朋友的房间数。所有 $$$x_i$$$ 都是不同的。
接下来的 $$$n-1$$$ 行包含走廊的描述,每行两个数字 $$$v_j$$$ 和 $$$u_j$$$ ($$$1 \le u_j, v_j \le n$$$) — 连接 $$$j$$$ 走廊的房间数量。所有走廊都是双向的。从任何房间,您都可以沿着走廊前往任何其他房间。
保证测试中所有测试用例的值 $$$n$$$ 之和不大于 $$$2\cdot10^5$$$。
输出
打印 $$$t$$$ 行,每行包含相应测试用例的答案。如果 Vlad 能够保证自己获胜,则测试用例的答案应该是“YES”,否则应该是“NO”。
您可以按照您想要的任何大小写打印每个字母(因此,例如,字符串“yEs”、“yes”、“Yes”和“YES”都将被识别为肯定答案)。
示例
输入 #1
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
输出 #1
YES NO YES NO
注意
在第一个测试用例中,无论他的朋友的策略如何,Vlad 都可以通过进入 $$$4$$$ 房间获胜。游戏可能是这样的:
弗拉德和朋友们原来的地点。弗拉德被标记为绿色,朋友们——被标记为红色。
一个时间单位后的位置。
游戏结束。
请注意,如果 Vlad 试图到达 $$$8$$$ 房间的出口,那么来自 $$$3$$$ 房间的朋友将能够抓住他。