题目描述

JOI 王国是一个由 $N$ 个岛屿组成的岛国，编号从 $1$ 到 $N$。这些岛屿通过 $N - 1$ 座桥相连，编号从 $1$ 到 $N - 1$。桥 $i\ (1 \leq i \leq N - 1)$ 双向连接岛屿 $A_i$ 和岛屿 $B_i$。可以通过若干座桥从任意一个岛屿到达另一个岛屿。在 JOI 王国，有 $M$ 个观光景点，编号从 $1$ 到 $M$。观光景点 $j\ (1 \leq j \leq M)$ 位于岛屿 $C_j$。有 $Q$ 位旅行者，他们计划参观 JOI 王国的观光景点。旅行者编号从 $1$ 到 $Q$。每位旅行者按以下方式旅行。

1. 旅行者选择一个岛屿 $x\ (1 \leq x \leq N)$。乘坐飞机，旅行者到达岛屿 $x$。

2. 旅行者进行若干次以下动作。动作的顺序和种类是任意的。

   • 旅行者选择当前岛屿上的一个观光景点，并参观。
   • 旅行者通过桥梁移动到另一个岛屿。

3. 乘坐飞机，旅行者离开 JOI 王国。旅行者 $k\ (1 \leq k \leq Q)$ 想要参观所有的观光景点 $L_k, L_{k + 1}, \ldots, R_k$。然而，由于预算有限，旅行者 $k$ 希望最小化至少访问一次的岛屿数量。

输入格式

从标准输入读取以下数据。

$N\ M\ Q$

$A_1\ B_1$

$A_2\ B_2$

$\vdots$

$A_{N-1}\ B_{N-1}$

$C_1\ C_2\ \cdots\ C_M$

$L_1\ R_1$

$L_2\ R_2$

$\vdots$

$L_Q\ R_Q$

输出格式

向标准输出写入 $Q$ 行。输出的第 $k$ 行 $(1 \leq k \leq Q)$ 应包含旅行者 $k$ 至少访问一次的岛屿的最小可能数量。

题目大意

给出一颗 $n$ 个节点的树，和一个长度为 $m$ 的序列 $a$，$q$ 次询问包含 $a_{l\cdots r}$ 中所有节点的最小联通块大小。

$n,m,q\le 10^5$

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

4
6

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

3
4
6
6
3
6
1
6
3

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

1
6
6
4
3
1
7
5
4

提示

【样例解释 #1】

旅行者 1 按以下方式旅行，并参观所有的观光景点 1, 2, 3。

1. 旅行者 1 到达岛屿 2。
2. 旅行者 1 参观岛屿 2 上的观光景点 1。
3. 旅行者 1 通过桥梁 1 从岛屿 2 移动到岛屿 1。
4. 旅行者 1 通过桥梁 2 从岛屿 1 移动到岛屿 3。
5. 旅行者 1 参观岛屿 3 上的观光景点 2。
6. 旅行者 1 通过桥梁 5 从岛屿 3 移动到岛屿 6。
7. 旅行者 1 参观岛屿 6 上的观光景点 3。
8. 旅行者 1 从岛屿 6 出发，离开 JOI 王国。

岛屿 1, 2, 3, 6 是旅行者 1 至少访问一次的四个岛屿。如果旅行者 1 至少访问一次的岛屿数量小于或等于 3，则不可能参观所有的观光景点 1, 2, 3。因此，第一行输出 4。旅行者 2 按以下方式旅行，并参观所有的观光景点 4, 5, 6。

1. 旅行者 2 到达岛屿 3。
2. 旅行者 2 通过桥梁 6 从岛屿 3 移动到岛屿 7。
3. 旅行者 2 参观岛屿 7 上的观光景点 6。
4. 旅行者 2 通过桥梁 6 从岛屿 7 移动到岛屿 3。
5. 旅行者 2 通过桥梁 2 从岛屿 3 移动到岛屿 1。
6. 旅行者 2 通过桥梁 1 从岛屿 1 移动到岛屿 2。
7. 旅行者 2 通过桥梁 3 从岛屿 2 移动到岛屿 4。
8. 旅行者 2 参观岛屿 4 上的观光景点 4。
9. 旅行者 2 通过桥梁 3 从岛屿 4 移动到岛屿 2。
10. 旅行者 2 通过桥梁 4 从岛屿 2 移动到岛屿 5。
11. 旅行者 2 参观岛屿 5 上的观光景点 5。
12. 旅行者 2 从岛屿 5 出发，离开 JOI 王国。

岛屿 1, 2, 3, 4, 5, 7 是旅行者 2 至少访问一次的六个岛屿。如果旅行者 2 至少访问一次的岛屿数量小于或等于 5，则不可能参观所有的观光景点 4, 5, 6。因此，第二行输出 6。此样例输入满足子任务 1, 2, 4, 5, 6 的约束。

岛屿 1, 2, 3, 4, 5, 7 是旅行者 2 至少访问一次的六个岛屿。如果旅行者 2 至少访问一次的岛屿数量小于或等于 5，则不可能参观所有的观光景点 4, 5, 6。因此，第二行输出 6。

此样例输入满足子任务 1, 2, 4, 5, 6 的约束。

【样例解释 #2】

此样例输入满足子任务 1, 2, 3, 6 的约束。

【样例解释 #3】

此样例输入满足子任务 1, 2, 6 的约束。

【数据范围】

• $1 \leq N \leq 100 000$。
• $1 \leq M \leq 100 000$。
• $1 \leq Q \leq 100 000$。
• $1 \leq A_i \leq N\ (1 \leq i \leq N - 1)$。
• $1 \leq B_i \leq N\ (1 \leq i \leq N - 1)$。
• 可以通过若干座桥从任意一个岛屿到达另一个岛屿。
• $1 \leq C_j \leq N\ (1 \leq j \leq M)$。
• $1 \leq L_k \leq R_k \leq M\ (1 \leq k \leq Q)$。
• 给定的值都是整数。

【子任务】

1. (5 分) $N \leq 300, M \leq 300, Q \leq 300$。
2. (5 分) $N \leq 2 000, M \leq 2 000, Q \leq 2 000$。
3. (7 分) $A_i = i, B_i = i + 1\ (1 \leq i \leq N - 1)$。
4. (18 分) $L_1 = 1, R_{k} + 1 = L_{k+1}\ (1 \leq k \leq Q - 1), R_Q = M$。
5. (24 分) $A_i = \lfloor\frac{i+1}2\rfloor, B_i = i + 1\ (1 \leq i \leq N-1)$。这里，$\lfloor x\rfloor$ 是不超过 x 的最大整数。
6. (41 分) 无额外约束。

题面翻译由 ChatGPT-4o 提供。