Rando-Vacances – Épreuve régionale 2022

Niveau 4

Énoncé

Un groupe d'amis part à la montagne. Ils veulent randonner deux jours et une nuit en tout. Pour préparer leur périple, ils souhaiteraient savoir combien de randonnées sont possibles.

Pour pouvoir dormir en sécurité, ils étudient des parcours passant par des refuges. Pour éviter toute mauvaise surprise, le meneur du groupe prévoit deux choix de refuges différents.

Il possède une carte de la zone avec chaque refuge numéroté. Plusieurs refuges peuvent avoir le même numéro, ce numéro est le type de refuge.

En plus de cela, il connait deux nombres correspondant à deux types de refuge. Nous appelerons ces nombres a et b dans la suite de l'exercice. Si l'un des refuges d'un des deux types est fermé, les refuges de l'autre type seront garantis ouverts.

Il remarque de plus que la carte représente un arbre binaire, les nœuds sont les refuges numérotés de leur type et les arêtes sont les possibles chemins de randonnées entre ces refuges. La racine est ainsi le refuge le plus haut dans la montagne.

Le point culminant de la randonnée est son point le plus haut. La racine étant le refuge au sommet de la montagne, plus un point est proche de la racine de l'arbre, plus il est élevé.

Le but est de compter le nombre de randonnées envisageables.

Une randonnée est composée d'un ou plusieurs chemins contigus. Deux randonnées sont différentes seulement si un chemin de l'une n'est pas dans l'autre. Le sens de randonnée n'a pas d'importance.

Une randonnée est envisageable si elle dispose à son point culminant, d'un chemin d'une unique arète reliant un refuge a à un refuge b, s'assurant ainsi que l'un des deux refuges soit ouvert. (Le point culminant et l'un de ses deux fils forment une paire a-b).

Pour résumer, une randonnée est considérée envisageable si :

  • Elle passe par un chemin (une arête) ayant un refuge de type a et un refuge de type b à ses extrémités.

  • L'un de ces refuges est le point culminant de la randonnée.

Autrement dit, la randonnée doit posséder un sommet numéroté a ayant un fils numéroté b ou inversement.

Entrée

L’entrée contiendra :

  • Sur la première ligne, un entier : n, le nombre de refuges.
  • Sur la ligne suivante, un entier : a, le numéro des refuges de type A.
  • Sur la ligne suivante, un entier : b, le numéro des refuges de type B.
  • Sur la ligne suivante, une liste de n entiers séparés par des espaces : v, les numéros de chaque refuge (le premier est la racine de l'arbre).
  • Sur les lignes suivantes, une liste de n éléments : e, les fils de chaque noeud.
    • Une ligne par élément de la liste : séparés par des espaces, un entier gauche (fils gauche (-1 si non présent)), et un entier droit (fils droit (-1 si non présent)).

L'arbre est garanti valide et binaire.

Sortie

Afficher le nombre de randonnées valides telles que décrites dans l'énoncé.

Contraintes

  • $1 \le n \le 10^5$
  • $1 \le a \le 10^5$
  • $1 \le b \le 10^5$
  • $1 \le v[ ] \le 10^5$
  • $A \ne B$

Contraintes d'exécution

Utilisation mémoire maximum
1000 kilo-octets
Temps d'exécution maximum
1000 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
7
5
2
5 4 2 1 2 2 4
2 3
4 5
6 7
-1 -1
-1 -1
-1 -1
-1 -1
Exemple de sortie
12
Commentaire

Par exemple, voici une carte contenant 7 refuges :

Exemple 1

Nous savons qu'un chemin reliant un refuge numéroté 5 à un refuge numéroté 2 situé au point culminant de la randonnée garantit l'un des deux refuges ouvert. Passer ici par le sommet ainsi que son fils droit (de numéro 2) garantit au groupe de pouvoir dormir. Voici chaque randonnée passant par ce chemin (notées de gauche à droite) :

  • 5, 2
  • 1, 4, 5, 2
  • 4, 5, 2
  • 1, 4, 5, 2, 4
  • 2, 4, 5, 2, 4
  • 1, 4, 5, 2, 2
  • 2, 4, 5, 2
  • 4, 5, 2, 2
  • 2, 4, 5, 2, 2
  • 5, 2, 2
  • 4, 5, 2, 4
  • 5, 2, 4

Il y a alors 12 randonnées distinctes pour cette carte.

Exemple d'entrée
9
5
2
8 5 4 2 1 2 2 4 42
-1 2
3 4
5 6
7 8
-1 9
-1 -1
-1 -1
-1 -1
-1 -1
Exemple de sortie
15
Commentaire

Exemple 2

Comme l'exemple 1, sauf que trois randonnées se sont ajoutées :

  • 42, 1, 4, 5, 2
  • 42, 1, 4, 5, 2, 2
  • 42, 1, 4, 5, 2, 4

Ici, le refuge numéro 5 n'est pas au point culminant de la montagne mais bien au point culminant de la randonnée.

Exemple d'entrée
10
5
2
42 2 3 1 1 9 6 5 8 7
2 3
4 5
-1 6
-1 -1
-1 -1
7 8
-1 -1
9 10
-1 -1
-1 -1
Exemple de sortie
0
Commentaire

Exemple 3

Aucune randonnée possible, le résultat est donc 0.