Universal Cup Judging System

Universal Cup

حد الوقت: 2.5 s حد الذاكرة: 512 MB مجموع النقاط: 100
الإحصائيات

Nie chodzi o pieniądze, chodzi o przekazanie wiadomości.

W sieci $n$ osób połączonych w strukturę drzewa osoba $1$ chce wysłać wiadomość do osoby $n$. Istnieje $10^9$ różnych języków ponumerowanych od $1$ do $10^9$. Osoba $i$ zna wszystkie języki z przedziału $[l_i, r_i]$.

Osoba $1$ zaczyna z kartką papieru i może zapisać początkową wiadomość w dowolnym języku, którym się posługuje. W każdej turze osoba trzymająca aktualnie kartkę może wykonać jedną z następujących czynności:

  • Przekazać kartkę sąsiedniej osobie w drzewie.
  • Jeśli rozumie język, w którym aktualnie napisana jest wiadomość na kartce, przetłumaczyć ją na dowolny inny znany sobie język (nadpisując oryginał).

Znajdź minimalną liczbę tur potrzebnych do tego, aby osoba $n$ otrzymała kartkę z wiadomością napisaną w języku, który rozumie.

Wejście

Pierwszy wiersz zawiera jedną liczbę całkowitą $n$ — liczbę osób.

Kolejne $n - 1$ wierszy zawiera po dwie liczby całkowite $u$ oraz $v$, opisujące krawędź pomiędzy osobami $u$ i $v$ w drzewie.

Kolejne $n$ wierszy zawiera po dwie liczby całkowite $l_i$ oraz $r_i$ — przedział opisujący języki, którymi posługuje się osoba $i$.

Wyjście

Wypisz jedną liczbę całkowitą — minimalną liczbę tur potrzebnych, aby osoba $n$ otrzymała wiadomość w języku, który rozumie.

Ograniczenia

  • $2 \le n \le 2 \cdot 10^5$,
  • $1 \le u, v \le n$ dla wszystkich krawędzi,
  • $u \neq v$ dla wszystkich krawędzi,
  • $1 \le l_i \le r_i \le 10^9$,
  • jest zagwarantowane, że każda osoba może wysłać wiadomość do każdej innej osoby (być może wymagając serii tłumaczeń).

Przykład 1

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

Uwagi

W przykładzie drzewo jest ścieżką.

Osoba $1$ zna języki $1, 2, 3$. Osoba $2$ zna języki $2, 3, 4$. Osoba $3$ zna języki $3, 4, 5$. Osoba $4$ zna języki $4, 5, 6$.

Jedno z optymalnych rozwiązań wygląda następująco. Najpierw osoba $1$ zapisuje wiadomość w języku $3$. Następnie kolejne osoby wykonują tury:

  1. Osoba $1$ przekazuje kartkę osobie $2$.
  2. Osoba $2$ tłumaczy wiadomość z języka $3$ na język $4$.
  3. Osoba $2$ przekazuje kartkę osobie $3$.
  4. Osoba $3$ przekazuje kartkę osobie $4$.

Osoba $4$ ma teraz wiadomość w języku $4$, który rozumie. Minimalna liczba potrzebnych tur wynosi cztery.

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.