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:
- Người $1$ chuyển tờ giấy cho người $2$.
- Người $2$ dịch thông điệp từ ngôn ngữ $3$ sang ngôn ngữ $4$.
- Người $2$ chuyển tờ giấy cho người $3$.
- 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.