Universal Cup Judging System

Universal Cup

시간 제한: 2.5 s 메모리 제한: 512 MB 총점: 100
통계

Vấn đề không phải là tiền bạc, mà là gửi đi một thông điệp.

Trong một mạng lưới gồm $n$ người được kết nối theo cấu trúc cây, người $1$ muốn gửi một thông điệp cho người $n$. Có $10^9$ ngôn ngữ khác nhau được đánh số từ $1$ đến $10^9$. Người $i$ nói được tất cả các ngôn ngữ trong đoạn $[l_i, r_i]$.

Người $1$ bắt đầu với một tờ giấy và có thể viết thông điệp ban đầu bằng bất kỳ ngôn ngữ nào mà họ nói được. Ở mỗi lượt, người hiện đang giữ tờ giấy có thể thực hiện một trong hai hành động sau:

  • Chuyển tờ giấy cho một người kề cạnh trên cây.
  • Nếu họ hiểu ngôn ngữ hiện đang được viết trên tờ giấy, dịch nó sang bất kỳ ngôn ngữ nào khác mà họ nói được (ghi đè lên bản gốc).

Hãy tìm số lượt tối thiểu để người $n$ nhận được tờ giấy có thông điệp được viết bằng ngôn ngữ mà họ hiểu.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên duy nhất $n$ — số lượng người.

$n - 1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u$ và $v$, mô tả một cạnh nối giữa người $u$ và người $v$ trên cây.

$n$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $l_i$ và $r_i$ — đoạn mô tả các ngôn ngữ mà người $i$ nói được.

Dữ liệu ra

In ra một số nguyên duy nhất — số lượt tối thiểu cần thiết để người $n$ nhận được thông điệp bằng ngôn ngữ mà họ hiểu.

Giới hạn

  • $2 \le n \le 2 \cdot 10^5$,
  • $1 \le u, v \le n$ với mọi cạnh,
  • $u \neq v$ với mọi cạnh,
  • $1 \le l_i \le r_i \le 10^9$,
  • đảm bảo rằng bất kỳ người nào cũng có thể gửi thông điệp cho bất kỳ người nào khác (có thể cần qua một loạt các bước dịch).

Ví dụ 1

4
1 2
2 3
3 4
1 3
2 4
3 5
4 6
4

Ghi chú

Trong ví dụ, cây là một đường thẳng.

Người $1$ nói các ngôn ngữ $1, 2, 3$. Người $2$ nói các ngôn ngữ $2, 3, 4$. Người $3$ nói các ngôn ngữ $3, 4, 5$. Người $4$ nói các ngôn ngữ $4, 5, 6$.

Một phương án tối ưu như sau. Đầu tiên, người $1$ viết thông điệp bằng ngôn ngữ $3$. Sau đó mọi người bắt đầu thực hiện các lượt:

  1. Người $1$ chuyển tờ giấy cho người $2$.
  2. Người $2$ dịch thông điệp từ ngôn ngữ $3$ sang ngôn ngữ $4$.
  3. Người $2$ chuyển tờ giấy cho người $3$.
  4. Người $3$ chuyển tờ giấy cho người $4$.

Người $4$ hiện có thông điệp bằng ngôn ngữ $4$ mà họ hiểu được. Số lượt tối thiểu cần thiết là bốn.

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.