Andy Jiang étudie les structures de données. Un jour, son ami Austin Zhu lui a confié une tâche sur les arbres.
Austin a fourni un arbre avec $N$ sommets, numérotés de $1$ à $N$. Chaque sommet $i$ possède une valeur $A_i$.
Pour chaque requête, Austin a demandé à Andy de considérer un chemin entre deux sommets $s_i$ et $t_i$, et de calculer combien de fois une valeur donnée $x_i$ apparaît sur ce chemin.
Andy a jeté un coup d'œil au problème et a pensé que cette tâche était trop facile pour lui.
Au lieu de simplement compter les occurrences, Andy a décidé de se lancer un défi supplémentaire. Pour chaque requête, il veut savoir comment la fréquence de $x_i$ se compare aux autres valeurs sur le même chemin.
Formellement, pour chaque requête $(s_i, t_i, x_i)$ :
- Considérez le chemin simple de $s_i$ à $t_i$.
- Soit $\text{cnt}(y)$ le nombre d'occurrences de la valeur $y$ sur ce chemin.
Andy définit le rang de $x_i$ comme $$1 + |\{y \mid \text{cnt}(y) > \text{cnt}(x_i)\}|.$$
C'est-à-dire, un plus le nombre de valeurs distinctes qui apparaissent plus fréquemment que $x_i$ sur le chemin. Notez qu'il est possible que la valeur $x_i$ n'apparaisse pas sur le chemin, c'est-à-dire $\text{cnt}(x_i) = 0$. Dans ce cas, vous devez retourner un plus le nombre de valeurs distinctes sur le chemin.
Dans certains cas de test, les requêtes sont données sous une forme encodée comme décrit ci-dessous.
Aidez Andy à calculer le rang de $x_i$ pour chaque requête.
Entrée
La première ligne contient trois entiers positifs $N$, $Q$ et $T$ ($1 \le N, Q \le 10^5$, $T \in \{0, 1\}$).
La deuxième ligne contient $N$ entiers $A_1, A_2, \dots, A_N$ ($1 \le A_i \le 10^9$).
Les $N - 1$ lignes suivantes contiennent chacune deux entiers $u_i, v_i$ ($1 \le u_i, v_i \le N$), représentant la $i$-ième arête.
Chacune des $Q$ lignes suivantes contient trois entiers $\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$), décrivant la $i$-ième requête.
Soit $\text{last}_0 = 0$. Pour chaque requête $i = 1, 2, \dots, Q$, les paramètres réels sont définis comme : $$s_i = ((\hat{s}_i + \text{last}_{i-1} \times T - 1) \pmod N) + 1$$ $$t_i = ((\hat{t}_i + \text{last}_{i-1} \times T - 1) \pmod N) + 1$$ $$x_i = ((\hat{x}_i + \text{last}_{i-1} \times T - 1) \pmod{10^9}) + 1$$
Après avoir calculé la réponse à la $i$-ième requête, définissez : $$\text{last}_i = \text{réponse à la } i\text{-ième requête.}$$
Il peut également être utile de noter que « mod » correspond à l'opérateur % dans la plupart des langages de programmation, indiquant le reste de la division. Par exemple, $5 \pmod 3 = 2$ et $17 \pmod 4 = 1$.
Sous-tâches
Le tableau suivant montre comment les 25 points disponibles sont répartis :
| Points | Bornes sur $N, Q$ | Bornes sur $T$ | Contraintes supplémentaires |
|---|---|---|---|
| 1 point | $1 \le N, Q \le 10^3$ | $T = 1$ | Aucune |
| 1 point | $1 \le N, Q \le 10^5$ | $T = 0$ | Tous les $s_i$ sont égaux |
| 4 points | $1 \le N, Q \le 10^5$ | $T = 1$ | Aucune |
| 4 points | $1 \le N, Q \le 10^5$ | $T = 0$ | $u_i = i$ et $v_i = i + 1$ |
| 5 points | $1 \le N, Q \le 10^5$ | $T = 1$ | $u_i = i$ et $v_i = i + 1$ |
| 3 points | $1 \le N, Q \le 10^5$ | $T = 0$ | Aucune |
| 7 points | $1 \le N, Q \le 10^5$ | $T = 1$ | Aucune |
Sortie
Pour chaque requête, affichez la réponse à la requête sur une nouvelle ligne.
Exemples
Exemples 1
Entrée :
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
Sortie :
2 1 4 1 1
Exemples 2
Entrée :
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
Sortie :
2 1 4 1 1