CF2155F Juan's Colorful Tree

胡安有一棵美丽的树，包含编号从 $1$ 到 $n$ 的 $n$ 个节点。还有 $k$ 种不同的颜色，编号从 $1$ 到 $k$。树中的每个节点 $u$ 都有自己的颜色集合 $C_u$。用 $s$ 表示所有集合大小的总和，即 $s = \sum_{i=1}^n |C_i|$。 有 $q$ 次查询，每次给出节点 $u$ 和 $v$。用 $P$ 表示从 $u$ 到 $v$ 的简单路径（包括端点）上的所有节点集合。对于每次查询，你需要计算以下值： $$ \left| \bigcap_{w \in P} C_w \right| $$ 也就是说，路径上所有节点的颜色集合的交集的基数。换句话说，计算在从 $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$。

对于每个测试用例，输出一行：按输入顺序输出所有查询的答案，用空格分隔。

在第一个测试用例中，有一棵 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| = |\{ 1, 2 \}| = 2$ - $|C_2 \cap C_1 \cap C_3| = |\{ 1, 2 \}| = 2$ - $|C_2 \cap C_1| = |\{ 1, 2, 5 \}| = 3$ - $|C_1| = |\{ 1, 2, 3, 4, 5 \}| = 5$