這無關金錢,而是為了傳遞一則訊息。
在一個由 $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$ 個人將紙傳給第 $2$ 個人。
- 第 $2$ 個人將訊息從語言 $3$ 翻譯成語言 $4$。
- 第 $2$ 個人將紙傳給第 $3$ 個人。
- 第 $3$ 個人將紙傳給第 $4$ 個人。
第 $4$ 個人現在拿到了以語言 $4$ 寫成的訊息,且他能理解該語言。所需的最少輪數為四輪。