CF2155F Juan's Colorful Tree

Juan has a beautiful tree with $ n $ nodes numbered from $ 1 $ to $ n $ . There are also $ k $ distinct colors numbered from $ 1 $ to $ k $ . Each node $ u $ in the tree has its own set $ C_u $ which contains colors. Let's denote with $ s $ the quantity $ \sum_{i=1}^n \left| C_i \right| $ . There are $ q $ queries where you will be given nodes $ u $ and $ v $ . Let $ P $ denote the set of all nodes in the simple path between $ u $ and $ v $ , inclusive. You are asked to calculate for each query the following quantity: $$$ \left| \bigcap_{w \in P} C_w \right| $$$ That is, the cardinality of the intersection of the sets of all the nodes in the path from $ u $ to $ v $ . In other words, calculate how many colors appear in every set on the path from $ u $ to $ v $ .

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows. The first line of each test case contains four integers $ n $ , $ k $ , $ s $ , and $ q $ ( $ 1 \le n, k, q \le 3 \cdot 10^5, 1 \le s \le \min (nk, 3 \cdot 10^5) $ ) — the number of nodes in the tree, the number of distinct colors, the sum of the cardinalities of all sets of colors, and the number of queries, respectively. The next $ n-1 $ lines each contain two integers $ u $ , $ v $ ( $ 1 \le u, v \le n $ ), indicating that there's an edge between nodes $ u $ and $ v $ . The next $ s $ lines each contain two integers $ v $ and $ x $ ( $ 1 \le v \le n, 1 \le x \le k $ ) indicating that color $ x $ is in $ C_v $ . All $ s $ lines are pairwise distinct. The next $ q $ lines each contain two integers $ u $ and $ v $ ( $ 1 \le u, v \le n $ ), indicating a query between nodes $ u $ and $ v $ . It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 3 \cdot 10^5 $ . It is guaranteed that the sum of $ k $ over all test cases does not exceed $ 3 \cdot 10^5 $ . It is guaranteed that the sum of $ s $ over all test cases does not exceed $ 3 \cdot 10^5 $ . It is guaranteed that the sum of $ q $ over all test cases does not exceed $ 3 \cdot 10^5 $ .

For each test case, output a line: the answer to all queries in the order they appear in the input, separated by spaces.

In the first test case, there is a tree of $ 3 $ nodes with edges $ (1, 3) $ and $ (2, 1) $ . The colors in the sets of each node are: - $ C_1 = \{ 1, 2, 3, 4, 5 \} $ - $ C_2 = \{ 1, 2, 5 \} $ - $ C_3 = \{ 1, 2 \} $ The $ 4 $ queries are between the pairs of nodes $ (1, 3) $ , $ (2, 3) $ , $ (1, 2) $ , $ (1, 1) $ and correspond to calculating the following quantities respectively: - $ \left| C_1 \cap C_3 \right| = \left| \{ 1, 2 \} \right| = 2 $ - $ \left| C_2 \cap C_1 \cap C_3 \right| = \left| \{ 1, 2 \} \right| = 2 $ - $ \left| C_2 \cap C_1 \right| = \left| \{ 1, 2, 5 \} \right| = 3 $ - $ \left| C_1 \right| = \left| \{ 1, 2, 3, 4, 5 \} \right| = 5 $