Universal Cup Judging System

Universal Cup

Limite de temps : 2.5 s Limite de mémoire : 512 MB Points totaux : 100
Statistiques

這無關金錢,而是為了傳遞一則訊息。

在一個由 $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.