Canadian Computing Olympiad 2026: Day 1, Problem 3

Andy Jiang is studying data structures. One day, his friend Austin Zhu gave him a task on trees.

Austin provided a tree with ~N~ vertices, numbered from ~1~ to ~N~. Each vertex ~i~ has a value ~A_i~.

For each query, Austin asked Andy to consider a path between two vertices ~s_i~ and ~t_i~, and compute how many times a given value ~x_i~ appears on that path.

Andy glanced at the problem and thought that this task was too easy for him.

Instead of just counting occurrences, Andy decided to challenge himself further. For each query, he wants to know how the frequency of ~x_i~ compares to other values on the same path.

Formally, for each query ~(s_i, t_i, x_i)~:

• Consider the simple path from ~s_i~ to ~t_i~.

• Let ~\mathrm{cnt}(y)~ be the number of occurrences of value ~y~ on this path.

Andy defines the rank of ~x_i~ as $$\displaystyle 1 + \left| \{ y \mid \mathrm{cnt}(y) > \mathrm{cnt}(x_i) \} \right|.$$

That is, one plus the number of distinct values that appear more frequently than ~x_i~ on the path. Note that it is possible the value ~x_i~ does not appear on the path, i.e. ~\mathrm{cnt}(x_i) = 0~. In this case, you should return 1 plus the number of distinct values on the path.

In some test cases, the queries are given in an encoded form as described below.

Help Andy compute the rank of ~x_i~ for each query.

Input Specification

The first line contains three positive integers ~N~, ~Q~, and ~T~ ~(1\le N, Q \le 10^5,\; T \in \{0,1\})~.

The second line contains ~N~ integers ~A_1, A_2, \dots, A_N~ ~(1 \le A_i \le 10^9)~.

The next ~N-1~ lines each contain two integers ~u_i, v_i~ ~(1 \le u_i, v_i \le N)~, representing the ~i~-th edge.

Each of the next ~Q~ lines contains three integers ~\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)~, describing the ~i~-th query.

Let ~\mathrm{last}_0 = 0~. For each query ~i = 1, 2, \dots, Q~, the actual parameters are defined as: $$\displaystyle \begin{align*} s_i &= ((\hat{s}_i + \mathrm{last}_{i-1} \times T - 1) \bmod N) + 1,\\ t_i &= ((\hat{t}_i + \mathrm{last}_{i-1} \times T - 1) \bmod N) + 1,\\ x_i &= ((\hat{x}_i + \mathrm{last}_{i-1} \times T - 1) \bmod 10^9) + 1. \end{align*}$$

After computing the answer to the ~i~-th query, set $$\displaystyle \mathrm{last}_i = \text{answer to the }i\text{-th query}.$$ It may also be useful to note that ~\bmod~ corresponds to the % operator in most programming languages, indicating the remainder after division. For example, ~5 \bmod 3 = 2~ and ~17 \bmod 4 = 1~.

The following table shows how the 25 available marks are distributed:

Marks Awarded	Bounds on ~N, Q~	Bounds on ~T~	Additional Constraints
1 mark	~1\le N, Q \le 10^3~	~T = 1~	None.
1 mark	~1\le N,Q \le 10^5~	~T = 0~	All ~s_i~ are equal.
4 marks		~T = 1~
4 marks		~T = 0~	~u_i=i~ and ~v_i=i+1~.
5 marks		~T = 1~
3 marks		~T = 0~	None.
7 marks		~T = 1~

Output Specification

For each query, output the answer to the query on a new line.

Sample Input 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

Sample Output 1

2
1
4
1
1

Sample Input 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

Sample Output 2

2
1
4
1
1