Coffre-fort – Qualification 2022

Level 4

Énoncé

Joseph Marchand doit ouvrir un coffre électronique sécurisé.

Le coffre contient un circuit complexe, décrit sous la forme d'un ensemble de puces, reliées entre elles par des fils. Il existe toujours exactement un chemin entre chaque paire de puces. Chaque puce envoie un signal $s_i$ au verrou lorsqu'elle est activée. Joseph Marchand tente de passer outre la sécurité du coffre et a besoin de votre aide pour calculer rapidement les effets de ses manipulations.

Il veut régulièrement connecter les deux bornes d'un générateur électrique à deux puces $a$ et $b$ du circuit, et se demande quel signal est envoyé au verrou du coffre suite à cette opération. Une puce $c$ est activée s'il existe un chemin de $a$ vers $b$ passant par $c$, qui ne repasse pas deux fois par le même fil. Le signal reçu par le verrou est alors le produit du signal envoyé par chaque puce activée, modulo $1671404011$ (car on ne peut pas représenter de trop grands nombres par un signal électrique).

Exemple

exemple

Entrée

L'entrée contiendra :

  • Sur la première ligne, un entier : N, nombre de puces.
  • Sur la ligne suivante, un entier : M, nombre de fils, égal à N-1
  • Sur la ligne suivante, un entier : R, nombre de questions.
  • Sur la ligne suivante, une liste de N entiers séparés par des espaces : signaux, liste des signaux.
  • Sur les lignes suivantes, une liste de M éléments : fils, liste des fils entre les puces.
    • Une ligne par élément de la liste : séparés par des espaces, un entier puce1 (première extrémité du fil), et un entier puce2 (seconde extrémité du fil).
  • Sur les lignes suivantes, une liste de R éléments : questions, liste des questions.
    • Une ligne par élément de la liste : séparés par des espaces, un entier puce a (première extrémité alimentée), et un entier puce b (seconde extrémité alimentée).

Sortie

Affiche le signal envoyé au coffre-fort pour chaque requête.

Contraintes

  • $1 \le N \le 100\,000$
  • $M=N-1$
  • $1 \le R \le 100\,000$
  • $0 \le s_i \le 1\,671\,404\,011$
  • $0 \le a_i, b_i, x_i, y_i < N$

Runtime constraints

Maximum memory usage
20000 kilobytes
Maximum execution time
1000 milliseconds

Input/output samples

Sample input
6
5
5
4 9 7 2 3 0
0 1
1 3
1 2
2 4
4 5
0 3
1 3
0 4
0 5
1 2
Sample output
72
18
756
0
63
Sample input
12
11
5
1671404010 1671404009 1371404010 1 3 8 2 7 10 4 0 6
0 1
2 0
3 2
3 4
9 3
5 3
7 5
5 6
8 4
9 10
11 10
1 8
7 7
6 8
9 7
2 10
Sample output
385444061
7
480
224
0

Submit your solution

You have to register or log in to be able to submit your solution.