돈이 문제가 아니라, 메시지를 전달하는 것이 핵심이다.
트리 구조로 연결된 $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$번 사람이 $2$번 사람에게 종이를 건네줍니다.
- $2$번 사람이 메시지를 언어 $3$에서 언어 $4$로 번역합니다.
- $2$번 사람이 $3$번 사람에게 종이를 건네줍니다.
- $3$번 사람이 $4$번 사람에게 종이를 건네줍니다.
이제 $4$번 사람은 자신이 이해할 수 있는 언어 $4$로 된 메시지를 받았습니다. 필요한 최소 턴 수는 4입니다.