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.