Universal Cup Judging System

Universal Cup

时间限制: 2.5 s 内存限制: 512 MB 总分: 100
统计

Det handlar inte om pengarna, det handlar om att skicka ett meddelande.

I ett nätverk av $n$ personer sammankopplade i en trädstruktur vill person $1$ skicka ett meddelande till person $n$. Det finns $10^9$ olika språk numrerade från $1$ till $10^9$. Person $i$ talar alla språk i intervallet $[l_i, r_i]$.

Person $1$ börjar med ett pappersark och kan skriva det ursprungliga meddelandet på vilket språk som helst som hen talar. I varje drag kan den person som för tillfället håller i pappret göra något av följande:

  • Skicka pappret vidare till en grannperson i trädet.
  • Om hen förstår språket som för närvarande står skrivet på pappret, översätta det till något annat språk som hen talar (och skriva över originalet).

Hitta det minsta antalet drag som krävs för att person $n$ ska få pappret med ett meddelande skrivet på ett språk som hen förstår.

Indata

Den första raden innehåller ett enda heltal $n$ — antalet personer.

De följande $n - 1$ raderna innehåller var och en två heltal $u$ och $v$, som beskriver en kant mellan personerna $u$ och $v$ i trädet.

De följande $n$ raderna innehåller var och en två heltal $l_i$ och $r_i$ — intervallet som beskriver de språk som person $i$ talar.

Utdata

Skriv ut ett enda heltal — det minsta antalet drag som behövs för att person $n$ ska få meddelandet på ett språk som hen förstår.

Begränsningar

  • $2 \le n \le 2 \cdot 10^5$,
  • $1 \le u, v \le n$ för alla kanter,
  • $u \neq v$ för alla kanter,
  • $1 \le l_i \le r_i \le 10^9$,
  • det garanteras att vilken person som helst kan skicka ett meddelande till vilken annan person som helst (eventuellt via en serie översättningar).

Exempel 1

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

Anmärkningar

I exemplet är trädet en väg.

Person $1$ talar språken $1, 2, 3$. Person $2$ talar språken $2, 3, 4$. Person $3$ talar språken $3, 4, 5$. Person $4$ talar språken $4, 5, 6$.

En optimal lösning är följande. Först skriver person $1$ meddelandet på språk $3$. Sedan börjar personerna göra sina drag:

  1. Person $1$ skickar pappret till person $2$.
  2. Person $2$ översätter meddelandet från språk $3$ till språk $4$.
  3. Person $2$ skickar pappret till person $3$.
  4. Person $3$ skickar pappret till person $4$.

Person $4$ har nu meddelandet på språk $4$, vilket hen förstår. Det minsta antalet drag som behövs är fyra.

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.