Prologin
2024
É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¶
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$