Universal Cup Judging System

Universal Cup

Límite de tiempo: 2.5 s Límite de memoria: 512 MB Puntuación total: 100
Estadísticas

돈이 문제가 아니라, 메시지를 전달하는 것이 핵심이다.

트리 구조로 연결된 $n$명의 사람들로 이루어진 네트워크에서, $1$번 사람이 $n$번 사람에게 메시지를 보내려고 합니다. $1$부터 $10^9$까지 번호가 매겨진 $10^9$개의 서로 다른 언어가 있습니다. $i$번 사람은 구간 $[l_i, r_i]$에 속하는 모든 언어를 구사할 수 있습니다.

$1$번 사람은 종이 한 장을 가지고 시작하며, 자신이 구사할 수 있는 아무 언어로든 처음 메시지를 작성할 수 있습니다. 매 턴마다 현재 종이를 가지고 있는 사람은 다음 중 하나를 수행할 수 있습니다.

  • 트리에서 이웃한 사람에게 종이를 건네줍니다.
  • 현재 종이에 적힌 언어를 이해할 수 있다면, 자신이 구사하는 다른 언어로 번역합니다 (기존 내용을 덮어씁니다).

$n$번 사람이 자신이 이해할 수 있는 언어로 작성된 메시지가 적힌 종이를 받기 위해 필요한 최소 턴 수를 구하세요.

입력

첫 번째 줄에는 사람의 수를 나타내는 정수 $n$이 주어집니다.

다음 $n - 1$개의 줄에는 각각 트리에서 $u$번 사람과 $v$번 사람을 잇는 간선을 나타내는 두 정수 $u$와 $v$가 주어집니다.

그다음 $n$개의 줄에는 각각 $i$번 사람이 구사하는 언어의 구간을 나타내는 두 정수 $l_i$와 $r_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

노트

예제에서 트리는 경로(path) 형태입니다.

$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$로 된 메시지를 받았습니다. 필요한 최소 턴 수는 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.