P16903 [CCO 2026] 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$ 的简单路径。 - 令 $\operatorname{cnt}(y)$ 表示值 $y$ 在这条路径上的出现次数。 Andy 将 $x_i$ 的 **排名** 定义为 $1 + |\{y \mid \operatorname{cnt}(y) > \operatorname{cnt}(x_i)\}|$。 也就是说，$1$ 加上路径上出现次数严格多于 $x_i$ 的不同值的个数。注意，$x_i$ 可能根本不在路径上，即 $\operatorname{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,\ldots,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$ 个查询。 令 $\operatorname{last}_0 = 0$。对每个查询 $i = 1,2,\ldots,Q$，实际参数按下式定义： $$ \begin{aligned} s_i &= ((\hat{s}_i + \operatorname{last}_{i-1} \times T - 1) \bmod N) + 1,\\ t_i &= ((\hat{t}_i + \operatorname{last}_{i-1} \times T - 1) \bmod N) + 1,\\ x_i &= ((\hat{x}_i + \operatorname{last}_{i-1} \times T - 1) \bmod 10^9) + 1. \end{aligned} $$ 计算完第 $i$ 个查询的答案后，令 $$ \operatorname{last}_i = \text{第 } i \text{ 个查询的答案}。 $$ 这里可能还需要说明，“mod” 对应于大多数编程语言中的 $\%$ 运算符，表示除法取余。例如，$5 \bmod 3 = 2$，$17 \bmod 4 = 1$。

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

以下表格展示了可获得的 $25$ 分的分配情况： | 分值 | $N,Q$ 的范围 | $T$ 的范围 | 额外限制 | |:-:|:-:|:-:|:-:| | $1$ 分 | $1 \le N,Q \le 10^3$ | $T=1$ | 无。 | | $1$ 分 | $1 \le N,Q \le 10^5$ | $T=0$ | 所有的 $s_i$ 均相等。 | | $4$ 分 | ^ | $T=1$ | ^ | | $4$ 分 | ^ | $T=0$ | $u_i=i$ 且 $v_i=i+1$。 | | $5$ 分 | ^ | $T=1$ | ^ | | $3$ 分 | ^ | $T=0$ | 无。 | | $7$ 分 | ^ | $T=1$ | ^ | 翻译由 DeepSeek V4 Pro 完成