呢個唔係錢嘅問題,而係要傳達一個訊息。
喺一個由 $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$ 寫嘅訊息,而佢係睇得明嘅。所需嘅最少輪數係四輪。