Universal Cup Judging System

Universal Cup

시간 제한: 2.5 s 메모리 제한: 512 MB 총점: 100
통계

Ce n'est pas une question d'argent, c'est une question de faire passer un message.

Dans un réseau de $n$ personnes reliées par une structure d'arbre, la personne $1$ veut envoyer un message à la personne $n$. Il existe $10^9$ langues différentes numérotées de $1$ à $10^9$. La personne $i$ parle toutes les langues de l'intervalle $[l_i, r_i]$.

La personne $1$ commence avec une feuille de papier et peut écrire le message initial dans n'importe quelle langue qu'elle parle. À chaque tour, la personne qui tient actuellement la feuille peut effectuer l'une des actions suivantes :

  • Passer la feuille à une personne voisine dans l'arbre.
  • Si elle comprend la langue actuellement écrite sur la feuille, la traduire dans n'importe quelle autre langue qu'elle parle (en écrasant l'original).

Trouvez le nombre minimal de tours pour que la personne $n$ reçoive la feuille avec un message écrit dans une langue qu'elle comprend.

Entrée

La première ligne contient un seul entier $n$ — le nombre de personnes.

Les $n - 1$ lignes suivantes contiennent chacune deux entiers $u$ et $v$, décrivant une arête entre les personnes $u$ et $v$ dans l'arbre.

Les $n$ lignes suivantes contiennent chacune deux entiers $l_i$ et $r_i$ — l'intervalle décrivant les langues parlées par la personne $i$.

Sortie

Affichez un seul entier — le nombre minimal de tours nécessaires pour que la personne $n$ reçoive le message dans une langue qu'elle comprend.

Contraintes

  • $2 \le n \le 2 \cdot 10^5$,
  • $1 \le u, v \le n$ pour toutes les arêtes,
  • $u \neq v$ pour toutes les arêtes,
  • $1 \le l_i \le r_i \le 10^9$,
  • il est garanti que n'importe quelle personne peut envoyer un message à n'importe quelle autre personne (en ayant éventuellement recours à une série de traductions).

Exemple 1

4
1 2
2 3
3 4
1 3
2 4
3 5
4 6
4

Notes

Dans l'exemple, l'arbre est un chemin.

La personne $1$ parle les langues $1, 2, 3$. La personne $2$ parle les langues $2, 3, 4$. La personne $3$ parle les langues $3, 4, 5$. La personne $4$ parle les langues $4, 5, 6$.

Une solution optimale est la suivante. Tout d'abord, la personne $1$ écrit le message dans la langue $3$. Ensuite, les personnes commencent à jouer leurs tours :

  1. La personne $1$ passe la feuille à la personne $2$.
  2. La personne $2$ traduit le message de la langue $3$ vers la langue $4$.
  3. La personne $2$ passe la feuille à la personne $3$.
  4. La personne $3$ passe la feuille à la personne $4$.

La personne $4$ a maintenant le message dans la langue $4$, qu'elle comprend. Le nombre minimal de tours nécessaires est de quatre.

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.