Universal Cup Judging System

Universal Cup

حد الوقت: 2.5 s حد الذاكرة: 512 MB مجموع النقاط: 100
الإحصائيات

Þetta snýst ekki um peningana, þetta snýst um að koma skilaboðum áleiðis.

Í neti $n$ manneskja sem eru tengdar saman í trjágrind vill manneskja $1$ senda skilaboð til manneskju $n$. Það eru $10^9$ ólík tungumál númeruð frá $1$ til $10^9$. Manneskja $i$ talar öll tungumál á bilinu $[l_i, r_i]$.

Manneskja $1$ byrjar með blað og getur skrifað upphaflegu skilaboðin á hvaða tungumáli sem hún talar. Í hverri umferð getur manneskjan sem heldur á blaðinu gert annað af eftirfarandi:

  • Rétt blaðið til nágranna síns í trénu.
  • Ef hún skilur tungumálið sem er skrifað á blaðið þá stundina, þýtt það yfir á hvaða annað tungumál sem hún talar (og skrifað yfir upprunalega textann).

Finnið lágmarksfjölda umferða til þess að manneskja $n$ fái blaðið með skilaboðum skrifuðum á tungumáli sem hún skilur.

Inntak

Fyrsta línan inniheldur eina heiltölu $n$ — fjölda manneskja.

Næstu $n - 1$ línur innihalda hver um sig tvær heiltölur $u$ og $v$, sem lýsa legg milli manneskja $u$ og $v$ í trénu.

Næstu $n$ línur innihalda hver um sig tvær heiltölur $l_i$ og $r_i$ — bilið sem lýsir tungumálunum sem manneskja $i$ talar.

Úttak

Prentið eina heiltölu — lágmarksfjölda umferða sem þarf til að manneskja $n$ fái skilaboðin á tungumáli sem hún skilur.

Takmarkanir

  • $2 \le n \le 2 \cdot 10^5$,
  • $1 \le u, v \le n$ fyrir alla leggi,
  • $u \neq v$ fyrir alla leggi,
  • $1 \le l_i \le r_i \le 10^9$,
  • það er tryggt að sérhver manneskja getur sent skilaboð til hvaða annarrar manneskju sem er (hugsanlega með röð þýðinga).

Dæmi 1

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

Athugasemdir

Í dæminu er tréð vegur.

Manneskja $1$ talar tungumál $1, 2, 3$. Manneskja $2$ talar tungumál $2, 3, 4$. Manneskja $3$ talar tungumál $3, 4, 5$. Manneskja $4$ talar tungumál $4, 5, 6$.

Ein besta lausnin er sem hér segir. Fyrst skrifar manneskja $1$ skilaboðin á tungumáli $3$. Síðan byrjar fólkið að gera:

  1. Manneskja $1$ réttir manneskju $2$ blaðið.
  2. Manneskja $2$ þýðir skilaboðin úr tungumáli $3$ yfir á tungumál $4$.
  3. Manneskja $2$ réttir manneskju $3$ blaðið.
  4. Manneskja $3$ réttir manneskju $4$ blaðið.

Manneskja $4$ er núna með skilaboðin á tungumáli $4$, sem hún skilur. Lágmarksfjöldi umferða sem þarf er fjórir.

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.