← 返回题目列表

Codeforces · 2155/F

F. 胡安的七彩树

中文机器翻译题面 查看原题

Juan有一棵美丽的树,其中有$$$n$$$节点,编号从$$$1$$$到$$$n$$$。还有 $$$k$$$ 不同的颜色,编号从 $$$1$$$ 到 $$$k$$$。树中的每个节点 $$$u$$$ 都有自己的包含颜色的集合 $$$C_u$$$。让我们用 $$$s$$$ 表示数量 $$$\sum_{i=1}^n \left| C_i \right|$$$。

有 $$$q$$$ 查询,您将获得节点 $$$u$$$ 和 $$$v$$$。让 $$$P$$$ 表示 $$$u$$$ 和 $$$v$$$ 之间的简单路径中的所有节点的集合,包括 $$$u$$$ 和 $$$v$$$。您需要为每个查询计算以下数量:$$\left| \bigcap_{w \in P} C_w \right|$$

即从$$$u$$$到$$$v$$$路径中所有节点的集合的交集的基数。换句话说,计算从 $$$u$$$ 到 $$$v$$$ 的路径上每组中出现了多少种颜色。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含四个整数 $$$n$$$、$$$k$$$、$$$s$$$ 和 $$$q$$$ ($$$1 \le n, k, q \le 3 \cdot 10^5, 1 \le s \le \min (nk, 3 \cdot 10^5)$$$) — 树中的节点数,分别是不同颜色的数量、所有颜色集的基数之和以及查询数量。

接下来的 $$$n-1$$$ 行每行包含两个整数 $$$u$$$、$$$v$$$ ($$$1 \le u, v \le n$$$),表示节点 $$$u$$$ 和 $$$v$$$ 之间有一条边。

接下来的 $$$s$$$ 行每行包含两个整数 $$$v$$$ 和 $$$x$$$ ($$$1 \le v \le n, 1 \le x \le k$$$) 表示颜色 $$$x$$$ 位于 $$$C_v$$$ 中。所有 $$$s$$$ 行都是成对不同的。

接下来的 $$$q$$$ 行每行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \le u, v \le n$$$),表示节点 $$$u$$$ 和 $$$v$$$ 之间的查询。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$3 \cdot 10^5$$$。

保证所有测试用例的 $$$k$$$ 总和不超过 $$$3 \cdot 10^5$$$。

保证所有测试用例的 $$$s$$$ 总和不超过 $$$3 \cdot 10^5$$$。

保证所有测试用例的 $$$q$$$ 总和不超过 $$$3 \cdot 10^5$$$。

输出

对于每个测试用例,输出一行:所有查询的答案按照它们在输入中出现的顺序排列,用空格分隔。

示例

输入
复制

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

输出
复制

2 2 3 5
1 1 1 2 1 2 1 1 1 0

注意

在第一个测试用例中,有一个由 $$$3$$$ 节点组成的树,其边为 $$$(1, 3)$$$ 和 $$$(2, 1)$$$。每个节点集合中的颜色为:

  • $$$C_1 = \{ 1, 2, 3, 4, 5 \}$$$
  • $$$C_2 = \{ 1, 2, 5 \}$$$
  • $$$C_3 = \{ 1, 2 \}$$$

$$$4$$$ 查询位于节点对 $$$(1, 3)$$$、$$$(2, 3)$$$、$$$(1, 2)$$$、$$$(1, 1)$$$ 之间,分别对应于计算以下数量:

  • $$$\左| C_1 \cap C_3 \right| = \左| \{ 1, 2 \} \right| = 2$$$
  • $$$\左| C_2 \cap C_1 \cap C_3 \right| = \左| \{ 1, 2 \} \right| = 2$$$
  • $$$\左| C_2 \cap C_1 \right| = \左| \{ 1, 2, 5 \} \right| = 3$$$
  • $$$\左| C_1 \右| = \左| \{ 1, 2, 3, 4, 5 \} \right| = 5$$$