Universal Cup Judging System

Universal Cup

Límite de tiempo: 2.5 s Límite de memoria: 512 MB Puntuación total: 100
Estadísticas

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:

  1. Person $1$ gibt das Papier an Person $2$ weiter.
  2. Person $2$ übersetzt die Nachricht von Sprache $3$ in Sprache $4$.
  3. Person $2$ gibt das Papier an Person $3$ weiter.
  4. 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.

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.