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

Анна графын онолд дуртай. Түүнд нүд болгон нь 1–ээс n хүртэл дугаарлагдсан, өөрийн гэсэн утга агуулсан мод байв.

Модны нийлбэр гэдэг нь бүх нүднүүдийн утгын нийлбэр байна. Хэрэв модны ирмэгийг огтолбол 2 жижиг мод үүсэх бөгөөд

2 модны ялгаа нь тэдгээр модны нийлбэрүүдийн ялгавар байна.

Өгөгдсөн модны аль ирмэгийг тайрвал үүсэх 2 модны нийлбэрүүдийн ялгавар нь хамгийн бага байх вэ?

Уг ялгаврыг олж буцаа.

Жишээ нь

Нүднүүдийн утга нь [1, 2, 3, 4,5 ,6 ] гэвэл нүднүүдийн дугаарлалт нь утгатайгаа ижил болж байна.

Дараах диаграммд үзүүлснээр ирмэгүүд нь [(1,2), (1, 3), (2, 6), (3, 4), (3, 5)] байна.

Дараах байдлаар тооцоолно.

Тайрах     Мод 1           Мод 2                     Абсолют

ирмэг     нийлбэр      нийлбэр                     ялгаа

1                  8                   13                         5

2                  9                  12                          3

3                  6                  15                          9

4                  4                  17                        13

5                  5                  16                        11

Хамгийн бага ялгаа нь 3

Санамж: 1 дугаартай нүдийг үндэс гэж үзнэ.

Функцын тодорхойлолт:

cutTheTree функцыг гүйцээж бич. Үүсэх 2 модноос гаргаж авч болох хамгийн бага абсолют ялгааг буцаа. /integer/

Параметрүүд:

 data: нүднүүдийн утгыг илэрхийлсэн integer утгаас бүрдсэн хүснэгт

edges: хос integer утгуудаас бүрдсэн 2 хэмжээст хүснэгт, хос бүр графын ирмэгийг илэрхийлнэ.

Оролтын формат

Эхний мөрөнд integer тоо n байна. Нүднүүдийн тоог илэрхийлнэ.

2 дахь мөрөнд зайгаар тусгаарлагдсан n ширхэг integer тоо байна. Тоо “u” тус бүр data[u] – н утгыг илэрхийлнэ.

Дараагийн n – 1 мөр болгонд зайгаар тусгаарлагдсан 2 ширхэг integer тоо u болон v байх бөгөөд u—v ирмэгийг илэрхийлнэ.

Хязгаарлалт

3 <= n <= 10⁵

1 <= data[u] <= 1001, 1<= u <= n.

Гаралтын формат

Боломжит хамгийн бага ялгааг илэрхийлсэн integer тоог агуулах 1 мөр.

Жишээ

Оролт

 6

100 200 100 500 100 600

1 2

2 3

2 5

4 5

5 6

Гаралт

400

Тайлбар

Бид үндсэн модыг дараах байдлаар дурсэлж болно.

n – 1 = 5 ирмэгийг бид огтолж болно.

1. ирмэг 1 – 2 -н үр дүнд d_1-/-2 = 1500 – 100 = 1400

2. ирмэг 2 – 3 -н үр дүнд d_2-/-3 = 1500 – 100 = 1400

3. ирмэг 2 – 5 -н үр дүнд d_2-/-5 = 1200 – 400 = 800

4. ирмэг 4 – 5 -н үр дүнд d_4-/-5 = 1100 – 500 = 600

5. ирмэг 5 – 6 -н үр дүнд d_5-/-6 = 1000 – 600 = 400

Хамгийн бага ялгаа нь 400.

Орчуулсан : Б.Баясгалантөгөлдөр АНУ