🔴 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

сурна.

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