АЛГОРИТМЫН ЦАГААН ТОЛГОЙ

Модны зангилаан дээр байх (a,b) хосыг дараах нөхцөл хангаж байвал ижил хос гэе.

 1. a зангилаа нь b зангилааны өвөг дээдэс

 2. abs(a - b) <= k.

Зангилаанууд нь 1,2,. . .,n гэсэн зүүлттэй модон дахь ижил хосын тоог олно уу.

Зурагт өгөгдсөн модны хувьд:

дараах өвөг дээдэс болон үр удмын хосууд гарна.

Pair             abs(a-b)                       Pair             abs(a-b)

1,2              1                                      3,4              1

1,3              2                                      3,5              2

1,4              3                                      3,6              3

1,5              4

1,6              5

Хэрэв k=3 гэж өгвөл abs(a-b) <= 3 нөхцөл хангах ижил хос 6 гарах нь.

Фунцийн тодорхойлолт

Доорх редакторын цонхонд similarPair функцийг гүйцээн бичнэ үү. Энэ функц шалгуурт нийцэж буй хосын тоог илэрхийлэх ганц бүхэл тоог буцаана.

similarPair дараах параметрүүдтэй.

n: зангилааны тоог илэрхийлэх бүхэл тоо

k: өгсөн бүхэл тоо

edges: хоорондоо холбогдсон зангилааны зүүлтийг илэрхийлдэг хоёр бүхэл тооноос бүрдэх элемент бүхий хоёр хэмжээст массив.

Оролтын хэлбэр

Эхний мөрөнд зайгаар тусгаарлагдсан n ба k хоёр бүхэл тоо өгөгдөнө. Энд n нь зангилааны тоо, k нь ижил хосын босго юм.

Дараагийн n-1 мөрд хос тоонууд зайгаар тусгаарлан өгөгдөнө. Энэ нь p[i], c[i] ирмэгтэй гэдгийг илэрхийлэх бөгөөд

p[i] нь эцэг зангилааны зүүлт бол c[i]  нь хүү зангилааны зүүлт юм.

Зааглалт

• 1 <= n <= 10^5

• 1 <= k <= n

• 1 <= p[i] ,c[i] <= n

Гаралтын хэлбэр

Ижил хосын тоог илэрхийлэх ганц бүхэл тоо байна.

Жишээ

Оролт

 5 2

3 2

3 1

1 4

1 5

Гаралт

4

Тайлбар

Нөхцөл хангах ижил хосууд (3,2), (3,1), (3,4), (3,5) байх учраас хариулт 4 юм.

(1,4), (1,5) хосууд байгаа боловч abs(a-b) <= k нөхцөлийг k=2 үед хангахгүй.

Орчуулсан : Р.Мижиддорж МУБИС, доктор