Universal Cup Judging System

Universal Cup

時間限制: 2.5 s 記憶體限制: 512 MB 總分: 100
统计

Мәселе ақшада емес, мәселе хабарлама жеткізуде.

Ағаш құрылымымен байланысқан $n$ адамнан тұратын желіде $1$-ші адам $n$-ші адамға хабарлама жібергісі келеді. $1$-ден $10^9$-ға дейін нөмірленген $10^9$ әртүрлі тіл бар. $i$-ші адам $[l_i, r_i]$ кесіндісіндегі барлық тілдерде сөйлейді.

$1$-ші адам бір парақ қағаздан бастайды және бастапқы хабарламаны өзі сөйлейтін кез келген тілде жаза алады. Әр жүрісте қағазды ұстап тұрған адам келесі әрекеттердің бірін орындай алады:

  • Қағазды ағаштағы көршілес адамға беру.
  • Егер ол қағазда қазір жазылған тілді түсінсе, оны өзі сөйлейтін кез келген басқа тілге аудару (түпнұсқаның үстінен жазу).

$n$-ші адам өзі түсінетін тілде жазылған хабарламасы бар қағазды алуы үшін қажетті ең аз жүрістер санын табыңыз.

Кіріс деректер

Бірінші жолда бір бүтін сан $n$ — адамдар саны берілген.

Келесі $n - 1$ жолдың әрқайсысында ағаштағы $u$ мен $v$ адамдарының арасындағы қырды сипаттайтын екі бүтін сан $u$ және $v$ берілген.

Келесі $n$ жолдың әрқайсысында $i$-ші адам сөйлейтін тілдерді сипаттайтын кесіндінің шеттері — екі бүтін сан $l_i$ және $r_i$ берілген.

Шығыс деректер

Бір бүтін санды — $n$-ші адам хабарламаны өзі түсінетін тілде алуы үшін қажетті ең аз жүрістер санын шығарыңыз.

Шектеулер

  • $2 \le n \le 2 \cdot 10^5$,
  • барлық қырлар үшін $1 \le u, v \le n$,
  • барлық қырлар үшін $u \neq v$,
  • $1 \le l_i \le r_i \le 10^9$,
  • кез келген адам кез келген басқа адамға (мүмкін, бірнеше аудармалар тізбегі арқылы) хабарлама жібере алатынына кепілдік беріледі.

Мысал 1

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

Ескертпелер

Мысалда ағаш жол болып табылады.

$1$-ші адам $1, 2, 3$ тілдерінде сөйлейді. $2$-ші адам $2, 3, 4$ тілдерінде сөйлейді. $3$-ші адам $3, 4, 5$ тілдерінде сөйлейді. $4$-ші адам $4, 5, 6$ тілдерінде сөйлейді.

Оңтайлы шешімдердің бірі келесідей. Алдымен $1$-ші адам хабарламаны $3$ тілінде жазады. Содан кейін адамдар жүрістер жасай бастайды:

  1. $1$-ші адам қағазды $2$-ші адамға береді.
  2. $2$-ші адам хабарламаны $3$ тілінен $4$ тіліне аударады.
  3. $2$-ші адам қағазды $3$-ші адамға береді.
  4. $3$-ші адам қағазды $4$-ші адамға береді.

Енді $4$-ші адамда өзі түсінетін $4$ тіліндегі хабарлама бар. Қажетті ең аз жүрістер саны — төрт.

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.