Universal Cup Judging System

Universal Cup

Süre Sınırı: 2.5 s Bellek Sınırı: 512 MB Toplam puan: 100
İstatistikler

No se trata del dinero, se trata de enviar un mensaje.

En una red de $n$ personas conectadas mediante una estructura de árbol, la persona $1$ quiere enviar un mensaje a la persona $n$. Hay $10^9$ idiomas diferentes numerados del $1$ al $10^9$. La persona $i$ habla todos los idiomas en el intervalo $[l_i, r_i]$.

La persona $1$ comienza con una hoja de papel y puede escribir el mensaje inicial en cualquier idioma que hable. En cada turno, la persona que tiene actualmente el papel puede hacer una de las siguientes acciones:

  • Pasar el papel a una persona vecina en el árbol.
  • Si entiende el idioma escrito actualmente en el papel, traducirlo a cualquier otro idioma que hable (sobrescribiendo el original).

Encuentra el número mínimo de turnos para que la persona $n$ reciba el papel con un mensaje escrito en un idioma que entienda.

Entrada

La primera línea contiene un solo entero $n$ — el número de personas.

Las siguientes $n - 1$ líneas contienen cada una dos enteros $u$ y $v$, que describen una arista entre las personas $u$ y $v$ en el árbol.

Las siguientes $n$ líneas contienen cada una dos enteros $l_i$ y $r_i$ — el intervalo que describe los idiomas que habla la persona $i$.

Salida

Imprime un solo entero — el número mínimo de turnos necesarios para que la persona $n$ reciba el mensaje en un idioma que entienda.

Restricciones

  • $2 \le n \le 2 \cdot 10^5$,
  • $1 \le u, v \le n$ para todas las aristas,
  • $u \neq v$ para todas las aristas,
  • $1 \le l_i \le r_i \le 10^9$,
  • se garantiza que cualquier persona puede enviar un mensaje a cualquier otra persona (posiblemente requiriendo una serie de traducciones).

Ejemplo 1

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

Notas

En el ejemplo, el árbol es un camino.

La persona $1$ habla los idiomas $1, 2, 3$. La persona $2$ habla los idiomas $2, 3, 4$. La persona $3$ habla los idiomas $3, 4, 5$. La persona $4$ habla los idiomas $4, 5, 6$.

Una solución óptima es la siguiente. Primero, la persona $1$ escribe el mensaje en el idioma $3$. Luego las personas comienzan a realizar turnos:

  1. La persona $1$ pasa el papel a la persona $2$.
  2. La persona $2$ traduce el mensaje del idioma $3$ al idioma $4$.
  3. La persona $2$ pasa el papel a la persona $3$.
  4. La persona $3$ pasa el papel a la persona $4$.

La persona $4$ ahora tiene el mensaje en el idioma $4$, el cual entiende. El número mínimo de turnos necesarios es cuatro.

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.