Language Barrier
Limits: 5 sec., 512 MiB
It’s not about the money, it’s about sending a message.
In a network of \(n\) people connected by a tree structure, person \(1\) wants to send a message to person \(n\). There are \(10^9\) different languages numbered from \(1\) to \(10^9\). Person \(i\) speaks all languages in the interval \([l_i, r_i]\).
Person \(1\) starts with a piece of paper and can write the initial message in any language they speak. On each turn, the person currently holding the paper can do one of the following.
Pass the paper to a neighboring person in the tree.
If they understand the language currently written on the paper, translate it to any other language they speak (overwriting the original).
Find the minimum number of turns for person \(n\) to receive the paper with a message written in a language they understand.
Input
The first line contains a single integer \(n\) – the number of people.
The next \(n-1\) lines each contain two integers \(u\) and \(v\), describing an edge between people \(u\) and \(v\) in the tree.
The next \(n\) lines each contain two integers \(l_i\) and \(r_i\) – the interval describing the languages that person \(i\) speaks.
Output
Print a single integer – the minimum number of turns needed for person \(n\) to receive the message in a language they understand.
Constraints
\(2 \le n \le 2 \cdot 10^5\)
\(1 \le u, v \le n\) for all edges,
\(u \ne v\) for all edges,
\(1 \le l_i \le r_i \le 10^9\),
it is guaranteed that any person can send a message to any other person (possibly requiring a series of translations).
Samples
| Input (stdin) | Output (stdout) |
|---|---|
| 4 1 2 2 3 3 4 1 3 2 4 3 5 4 6 | 4 |
Notes
In the sample, the tree is a path.
Person \(1\) speaks languages \(1\), \(2\), \(3\). Person \(2\) speaks languages \(2\), \(3\), \(4\). Person \(3\) speaks languages \(3\), \(4\), \(5\). Person \(4\) speaks languages \(4\), \(5\), \(6\).
One optimal solution is as follows. First, person \(1\) writes the message in language \(3\). Then the people start to make turns.
Person \(1\) passes the paper to person \(2\).
Person \(2\) translates the message from language \(3\) into language \(4\).
Person \(2\) passes the paper to person \(3\).
Person \(3\) passes the paper to person \(4\).
Person \(4\) now has the message in language \(4\), which they understand. The minimum number of turns needed is four.
Submit a solution
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|