Þ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:
- Manneskja $1$ réttir manneskju $2$ blaðið.
- Manneskja $2$ þýðir skilaboðin úr tungumáli $3$ yfir á tungumál $4$.
- Manneskja $2$ réttir manneskju $3$ blaðið.
- 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.