Universal Cup Judging System

Universal Cup

実行時間制限: 2.5 s メモリ制限: 512 MB 満点: 100
統計

金の問題じゃない、メッセージを伝えることが重要なんだ。

木構造でつながった $n$ 人のネットワークにおいて、人 $1$ が人 $n$ にメッセージを送りたいと考えています。$1$ から $10^9$ までの番号が付けられた $10^9$ 種類の異なる言語があります。人 $i$ は区間 $[l_i, r_i]$ に含まれるすべての言語を話せます。

人 $1$ は最初に1枚の紙を持っており、自分が話せる任意の言語で最初のメッセージを書くことができます。各ターンにおいて、現在紙を持っている人は次のいずれか1つを行うことができます。

  • 木において隣接する人に紙を渡す。
  • 現在紙に書かれている言語を理解できる場合、それを自分が話せる他の任意の言語に翻訳する(元の文章を上書きする)。

人 $n$ が自分の理解できる言語で書かれたメッセージの載った紙を受け取るために必要な最小ターン数を求めてください。

入力

1行目には、人数を表す単一の整数 $n$ が与えられます。

続く $n - 1$ 行にはそれぞれ、木における人 $u$ と人 $v$ の間の辺を表す2つの整数 $u$ と $v$ が与えられます。

さらに続く $n$ 行にはそれぞれ、人 $i$ が話せる言語の区間を表す2つの整数 $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

注記

入力例では、木はパス(一本道)になっています。

人 $1$ は言語 $1, 2, 3$ を話せます。人 $2$ は言語 $2, 3, 4$ を話せます。人 $3$ は言語 $3, 4, 5$ を話せます。人 $4$ は言語 $4, 5, 6$ を話せます。

最適な解の1つは以下の通りです。まず、人 $1$ が言語 $3$ でメッセージを書きます。その後、ターンを進めていきます。

  1. 人 $1$ が人 $2$ に紙を渡す。
  2. 人 $2$ がメッセージを言語 $3$ から言語 $4$ に翻訳する。
  3. 人 $2$ が人 $3$ に紙を渡す。
  4. 人 $3$ が人 $4$ に紙を渡す。

これで人 $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.