#5749. 「CCO 2026」Beyond Counting

标签: 传统 | 时间限制: 5000 ms | 内存限制: 1024 MiB |

题目描述

译自 CCO 2026 Day1 T3「Beyond Counting」。

Andy Jiang 正在学习数据结构。有一天，他的朋友 Austin Zhu 给了他一个关于树的任务。

Austin 提供了一棵包含 $N$ 个顶点的树，顶点编号从 $1$ 到 $N$。每个顶点 $i$ 都有一个权值 $A_i$。

对于每个询问，Austin 要求 Andy 考虑顶点 $s_i$ 和 $t_i$ 之间的路径，并计算给定值 $x_i$ 在该路径上出现了多少次。

Andy 扫了一眼题目，觉得这个任务对他来说太简单了。

不仅仅是统计出现次数，Andy 决定进一步挑战自己。对于每个询问，他想知道 $x_i$ 的出现频率与同一路径上其他值的频率相比如何。

形式化地，对于每个询问 $(s_i, t_i, x_i)$：

• 考虑从 $s_i$ 到 $t_i$ 的简单路径。
• 令 $\mathrm{cnt}(y)$ 为该路径上权值 $y$ 的出现次数。

Andy 将 $x_i$ 的排名（rank）定义为：

$$1 + |\{y \mid \mathrm{cnt}(y) > \mathrm{cnt}(x_i)\}|$$

也就是说，排名等于「比 $x_i$ 出现次数更多的不同数值的个数」加 $1$。请注意，$x_i$ 可能完全没有在路径上出现（即 $\mathrm{cnt}(x_i) = 0$）。在这种情况下，你应该返回「路径上不同数值的个数」加 $1$。

在某些测试用例中，询问会以如下所述的加密形式给出。

请帮助 Andy 计算每个询问中 $x_i$ 的排名。

输入格式

第一行包含三个正整数 $N, Q$ 和 $T$ $(1 \le N, Q \le 10^5, T \in \{0, 1\})$。

第二行包含 $N$ 个整数 $A_1, A_2, \dots, A_N$ $(1 \le A_i \le 10^9)$。

接下来 $N-1$ 行，每行包含两个整数 $u_i, v_i$ $(1 \le u_i, v_i \le N)$，表示第 $i$ 条边。

接下来的 $Q$ 行，每行包含三个整数 $\hat{s}_i, \hat{t}_i, \hat{x}_i$ $(1 \le \hat{s}_i, \hat{t}_i \le N, 1 \le \hat{x}_i \le 10^9)$，描述第 $i$ 个询问。

令 $\mathrm{last}_0 = 0$。对于询问 $i = 1, 2, \dots, Q$，实际参数定义如下：

$$\begin{aligned} s_i & =\left(\left(\hat{s}_i+\mathrm{ last }_{i-1} \times T-1\right) \bmod N\right)+1 \\ t_i & =\left(\left(\hat{t}_i+\mathrm{ last }_{i-1} \times T-1\right) \bmod N\right)+1 \\ x_i & =\left(\left(\hat{x}_i+\mathrm{ last }_{i-1} \times T-1\right) \bmod 10^9\right)+1 \end{aligned}$$

其中 $\oplus$ 表示按位异或（XOR）运算。在计算出第 $i$ 个询问的答案后，令 $\mathrm{last}_i$ 等于该答案。

提示：$\bmod$ 对应于大多数编程语言中的 $\%$ 运算符，表示除法后的余数。例如，$5 \bmod 3 = 2$ 且 $17 \bmod 4 = 1$。

输出格式

对于每个询问，在新的一行中输出询问的答案。

样例 1

输入

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

输出

2
1
4
1
1

样例 2

输入

5 5 1
1 2 3 4 4
4 3
2 5
1 3
3 2
4 5 3
2 3 2
3 4 4
2 1 999999997
5 4 3

输出

2
1
4
1
1

数据范围与提示

详细子任务附加限制及分值如下表所示。

子任务	分值	$N, Q$ 范围	$T$ 范围	附加限制
$1$	$4$	$1 \le N, Q \le 10^3$	$T = 1$	无
$2$	$4$	$1 \le N, Q \le 10^5$	$T = 0$	所有 $s_i$ 均相等
$3$	$16$		$T = 1$	无
$4$	$16$		$T = 0$	$u_i = i$ 且 $v_i = i+1$
$5$	$20$		$T = 1$	无
$6$	$12$		$T = 0$
$7$	$28$		$T = 1$