Codeforces Round #804 (Div. 2)
5 өдрийн дараа |
E. Ойрхон оройнууд
хугацааны хязгаарлалт 5 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Танд $n$ оройтой жинтэй мод байгаа. Ирмэг бүр нь сөрөг биш жинтэй. Модны замын урт гэдэг нь аль ч хоёр оройн хоорондох ирмэгийн тоо юм. Замын нийт жинд бүх оройнууд агуулагдана.
Хоёр оройндууд нь хэрэв ойрхон байгай бол эдгээрийн хоорондох замын урт нь $l$-ээс их мөн эдгээрийн хоорондох замын жин нь $w$-аас их байна. Хос $v, u$ $(v < u)$ оройнуудыг тоолно, эдгээр $v$ ба $u$ оройнууд нь ойрхон байна.
Оролт
Эхний мөрөнд гурван бүхэл $n$, $l$ ба $w$ $(1 ≤ n ≤ 10^{5}, 1 ≤ l ≤ n, 0 ≤ w ≤ 10^{9})$ тоонууд агуулагдана. Дараагийн $n - 1$ мөрөнд гурван оройны тодорхойлолт агуулагдана. $i$-р мөрөнд хоёр бүхэл $p_{i}, w_{i}$ $(1 ≤ p_{i} < (i + 1), 0 ≤ w_{i} ≤ 10^{4})$ тоонууд агуулагдах ба энэ нь $i$-р орой нь $(i + 1)$ оройтой ирмэгээр холбогдсонг $p_{i}$-р илэрхийлэх ба $w_{i}$ жинтэй.
Модны оройнуудыг $1$-ээс $n$ хүртэл дугаарласан гэж үзнэ.
Гаралт
Нэг мөрөнд ойрхон хос оройнуудын тоог хэвлэнэ.
С++ хэлний оролт гаралтын хэлбэрт $\%lld$ буюу тодорхойлбол 64-bit бүхэл тоог бүү хэрэглээрэй. Харин $cin$, $cout$ урсгал эсвэл $\%I64d$ хэлбэрийг ашиглавал тохиромжтой.
Орчуулсан: Даариймаа
Жишээ тэстүүд
Оролт
4 4 6 1 3 1 4 1 3
Гаралт
4
Оролт
6 2 17 1 3 2 5 2 13 1 6 5 9
Гаралт
9