? Editorial --- Kingdom Defense Planning (Сурагчдад ойлгомжтой тайлбар)

? Бодлогын зорилго

Бидэнд мод (tree) өгөгдөнө. Хот бүр үнэ цэнэтэй.

Бид яг K хот сонгоно.

? Нийт оноо: - Сонгосон хотуудын value нийлбэр - Хоорондын зай (distance)-г хасна

? Энгийнээр ойлговол

• Илүү их value авахыг хүснэ ✅
• Гэхдээ хол байрласан хотууд penalty өгнө ❌

? Иймээс: "ойрхон, ашигтай хотуудыг сонгох"

❗ Яагаад хэцүү вэ?

Хэрвээ бүх хосыг шалгавал: - O(K²) болно ❌

? Гол санаа (хамгийн чухал!)

Tree дээр зайг edge бүрээр тооцож болно.

? Нэг edge (зам) авч үзье:

Хэрвээ: - нэг талд i хот - нөгөө талд j хот байвал

? penalty = i × j × w

? DP санаа

dp[u][k] = u-ийн subtree-с k хот сонгох хамгийн их оноо

? Merge хийх

Child-уудыг нэгтгэхдээ:

dp[u][i] + dp[v][j] - i × j × w

? DFS ашиглана

dfs(u): dp[u] эхлүүлнэ child бүр дээр merge хийнэ

⚡ Яагаад optimization хэрэгтэй вэ?

Naive merge: → O(K²) ❌

? Small-to-large ашиглана: - жижиг vector-г том руу merge

? Жишээ ойлголт

Хоёр хэсэг: - 2 хот - 3 хот

? хооронд penalty: 2 × 3 × w

⚠️ Алдаа гаргах магадлалтай

• ❌ overflow (i × j × w)
• ❌ merge буруу
• ❌ dp хэмжээ хэтрэх

? Хариу

dp[root][K]

? Дүгнэлт

Энэ бодлогоор:

• Tree DP
• Merge
• Optimization

сурна.

? Олимпиадын түвшний бодлого ?