Es geht nicht ums Geld, es geht darum, eine Botschaft zu senden.
In einem Netzwerk von $n$ Personen, die über eine Baumstruktur verbunden sind, möchte Person $1$ eine Nachricht an Person $n$ senden. Es gibt $10^9$ verschiedene Sprachen, die von $1$ bis $10^9$ nummeriert sind. Person $i$ spricht alle Sprachen im Intervall $[l_i, r_i]$.
Person $1$ beginnt mit einem Blatt Papier und kann die ursprüngliche Nachricht in einer beliebigen Sprache verfassen, die sie spricht. In jedem Zug kann die Person, die das Papier gerade hält, eine der folgenden Aktionen ausführen:
- Das Papier an eine benachbarte Person im Baum weitergeben.
- Wenn sie die aktuell auf dem Papier geschriebene Sprache versteht, diese in eine beliebige andere Sprache übersetzen, die sie spricht (wobei das Original überschrieben wird).
Bestimme die minimale Anzahl an Zügen, damit Person $n$ das Papier mit einer Nachricht erhält, die in einer für sie verständlichen Sprache verfasst ist.
Eingabe
Die erste Zeile enthält eine einzelne ganze Zahl $n$ — die Anzahl der Personen.
Die nächsten $n - 1$ Zeilen enthalten jeweils zwei ganze Zahlen $u$ und $v$, die eine Kante zwischen den Personen $u$ und $v$ im Baum beschreiben.
Die nächsten $n$ Zeilen enthalten jeweils zwei ganze Zahlen $l_i$ und $r_i$ — das Intervall, das die Sprachen beschreibt, die Person $i$ spricht.
Ausgabe
Gib eine einzige ganze Zahl aus — die minimale Anzahl an Zügen, die benötigt wird, damit Person $n$ die Nachricht in einer Sprache erhält, die sie versteht.
Bedingungen
- $2 \le n \le 2 \cdot 10^5$,
- $1 \le u, v \le n$ für alle Kanten,
- $u \neq v$ für alle Kanten,
- $1 \le l_i \le r_i \le 10^9$,
- es ist garantiert, dass jede Person jeder anderen Person eine Nachricht senden kann (möglicherweise über eine Reihe von Übersetzungen).
Beispiel 1
4
1 2
2 3
3 4
1 3
2 4
3 5
4 6
4
Hinweise
Im Beispiel ist der Baum ein Pfad.
Person $1$ spricht die Sprachen $1, 2, 3$. Person $2$ spricht die Sprachen $2, 3, 4$. Person $3$ spricht die Sprachen $3, 4, 5$. Person $4$ spricht die Sprachen $4, 5, 6$.
Eine optimale Lösung sieht wie folgt aus. Zuerst schreibt Person $1$ die Nachricht in Sprache $3$. Dann beginnen die Personen mit ihren Zügen:
- Person $1$ gibt das Papier an Person $2$ weiter.
- Person $2$ übersetzt die Nachricht von Sprache $3$ in Sprache $4$.
- Person $2$ gibt das Papier an Person $3$ weiter.
- Person $3$ gibt das Papier an Person $4$ weiter.
Person $4$ hat nun die Nachricht in Sprache $4$, die sie versteht. Die minimale Anzahl benötigter Züge beträgt vier.