Universal Cup Judging System

Universal Cup

時間限制: 2.5 s 記憶體限制: 512 MB 總分: 100
统计

Дело не в деньгах, дело в том, чтобы отправить послание.

В сети из $n$ человек, соединённых в виде дерева, человек $1$ хочет отправить сообщение человеку $n$. Существует $10^9$ различных языков, пронумерованных от $1$ до $10^9$. Человек $i$ владеет всеми языками из отрезка $[l_i, r_i]$.

Вначале у человека $1$ есть листок бумаги, и он может написать исходное сообщение на любом языке, которым владеет. На каждом ходу человек, у которого сейчас находится листок, может сделать одно из следующих действий:

  • Передать листок соседнему по дереву человеку.
  • Если он понимает язык, на котором сейчас написано сообщение на листке, перевести его на любой другой язык, которым он владеет (переписав поверх старого текста).

Найдите минимальное количество ходов, за которое человек $n$ сможет получить листок с сообщением, написанным на понятном ему языке.

Входные данные

Первая строка содержит одно целое число $n$ — количество людей.

Следующие $n - 1$ строк содержат по два целых числа $u$ и $v$, описывающих ребро между людьми $u$ и $v$ в дереве.

Следующие $n$ строк содержат по два целых числа $l_i$ и $r_i$ — отрезок языков, которыми владеет человек $i$.

Выходные данные

Выведите одно целое число — минимальное количество ходов, необходимое для того, чтобы человек $n$ получил сообщение на понятном ему языке.

Ограничения

  • $2 \le n \le 2 \cdot 10^5$,
  • $1 \le u, v \le n$ для всех рёбер,
  • $u \neq v$ для всех рёбер,
  • $1 \le l_i \le r_i \le 10^9$,
  • гарантируется, что любой человек может отправить сообщение любому другому человеку (возможно, с помощью серии переводов).

Пример 1

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

Примечания

В примере дерево представляет собой путь.

Человек $1$ знает языки $1, 2, 3$. Человек $2$ знает языки $2, 3, 4$. Человек $3$ знает языки $3, 4, 5$. Человек $4$ знает языки $4, 5, 6$.

Одно из оптимальных решений выглядит так. Сначала человек $1$ пишет сообщение на языке $3$. Затем люди начинают делать ходы:

  1. Человек $1$ передаёт листок человеку $2$.
  2. Человек $2$ переводит сообщение с языка $3$ на язык $4$.
  3. Человек $2$ передаёт листок человеку $3$.
  4. Человек $3$ передаёт листок человеку $4$.

Теперь у человека $4$ есть сообщение на языке $4$, который он понимает. Минимальное необходимое количество ходов равно четырём.

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.