UOJ Logo Universal Online Judge

UOJ

好评差评[+15]

#722. 【JOISC2022】监狱

附件下载 统计

在 JOI 王国，安保最严格的地方就是 IOI 监狱。IOI 监狱中有 N 个房间，以 1,…,N 编号。其中有 N−1 条通道。第 i (1≤i≤N−1) 条通道双向地连接房间 Ai 和 Bi。任意两个房间都可以相互到达。

IOI 监狱中有 M 个囚犯，以 1,…,M 编号。第 j (1≤j≤M) 个囚犯的卧室和工作室分别是房间 Sj,Tj。一个囚犯可能在另一个囚犯的卧室工作。然而，每个房间最多成为一个囚犯的卧室，一个囚犯的工作室。

一天早上，这 M 个囚犯需要从他们的卧室移动到他们的工作室。典狱长 APIO 先生需要按如下方式指示囚犯移动：

指令：选择一个囚犯，然后命令他从当前所在的房间移动到一个与该房间有直接连边的房间。为了避免囚犯交流，不允许将囚犯移动到有其他囚犯在的房间。

为了尽早开始工作，APIO 先生想知道，是否存在一种给出任意条指令的方案使得每个囚犯以最短路径从卧室到达工作室。

请编写一个程序，在给定如上房间、通道和罪犯的所有信息后判断是否存在满足条件的方案。

输入格式

每个测试点包含多组测试数据。

第一行一个整数 Q，表示这个测试点包含 Q 组测试数据。

对于每组测试数据：

第一行一个整数 N，表示房间个数。

接下来 N−1 行每行两个整数 Ai,Bi 表示通道连接房间的编号。

接下来一行一个整数 M 表示囚犯个数。

接下来 M 行，每行两个整数 Si,Ti 表示囚犯的卧室和工作室。

输出格式

输出 Q 行，第 i 行 表示对于第 i 组测试数据，如果存在一种满足题意的方案，输出 Yes, 否则输出 No。

样例一

input

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

output

Yes

explanation

可以通过发送如下指令完成任务：

  1. 让囚犯 2 从 4 号房间移动到 5 号房间。
  2. 让囚犯 1 从 3 号房间移动到 4 号房间。
  3. 让囚犯 2 从 5 号房间移动到 6 号房间。
  4. 让囚犯 2 从 6 号房间移动到 7 号房间。
  5. 让囚犯 2 从 7 号房间移动到 8 号房间。

这组样例满足所有子任务的限制。

样例二

input

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

output

Yes
No

explanation

对于第一组数据，可以通过如下指令完成任务：

  1. 让囚犯 1 从 4 号房间移动到 3 号房间。
  2. 让囚犯 1 从 3 号房间移动到 2 号房间。
  3. 让囚犯 2 从 5 号房间移动到 4 号房间。
  4. 让囚犯 2 从 4 号房间移动到 3 号房间。
  5. 让囚犯 2 从 3 号房间移动到 6 号房间。
  6. 让囚犯 1 从 2 号房间移动到 1 号房间。
  7. 让囚犯 2 从 6 号房间移动到 7 号房间。

对于第二组数据，不存在一组指令能完成任务。

这组样例满足子任务 3,4,5,6,7 的限制。

样例三

见附件下载中的 ex_jail3.in 和 ex_jail3.ans，这组样例满足子任务 1,3,4,5,6,7 的限制。

数据范围与提示

  • 1≤Q≤1000
  • 1≤N≤120000
  • 1≤Ai<Bi≤N (i∈[1,N−1])
  • 2≤M≤N
  • 1≤Si,Ti≤N (i∈[1,M])
  • Si (i∈[1,M]) 互不相同。
  • Ti (i∈[1,M]) 互不相同。
  • Si≠Ti (i∈[1,M])
  • 任意两个房间之间可以通过给定道路互相到达。
  • 对于某个测试点的所有测试数据，N 的总和不超过 120000。

Subtasks

  1. (5 points) Ai=i,Bi=i+1 (i∈[1,N−1])
  2. (5 points) Q≤20,N≤250,M=2
  3. (16 points) Q≤20,N≤250,M≤6
  4. (28 points) Q≤20,N≤250,M≤100
  5. (12 points) Q≤20,M≤500
  6. (11 points) 任意两个房间之间都可以通过不超过 20 条道路到达。
  7. (23 points) 无特殊限制。

时间限制：4s

空间限制：1GB

Server time: 2025-04-16 22:22:39