Daraxtda DP — bu DFS-daraxtidagi uning bolalari qiymatlari asosida cho‘qqidagi qiymatlar hisoblanadigan masalalar sinfi.
Diametr — daraxtning ikki cho‘qqisi orasidagi maksimal oddiy yo‘l uzunligi.
Klassik DP-g‘oya:
Har bir cho‘qqi uchun hisoblaymiz:
Unda orqali o‘tuvchi yo‘l:
Global diametr — barcha bo‘yicha maksimum.
Har bir cho‘qqi uchun u orqali o‘tuvchi maksimal yo‘l uzunligini topish kerak.
Cho‘qqi orqali yo‘l quyidagicha ketishi mumkin:
Shuning uchun rerooting DP qilinadi:
Juftlashtirish — umumiy cho‘qqilari bo‘lmagan qirralar to‘plami.
Daraxt bo‘yicha DP:
cho‘qqi uchun hisoblaymiz:
O‘tishlar:
Natija:
Ildizdagi javob:
Bu da daraxtda maximum matching klassik masalasi.
Shuningdek, shuni ham qayd etamizki, har bir paytda barg olinib, imkon boricha ajdod bilan match qilinadigan ochko‘z yechim mavjud. Buni bitta DFS o‘tishi yordamida amalga oshirish mumkin.
Istalgan cho‘qqini tanlaymiz.
Unda yo‘li — daraxt diametri.
Daraxt cho‘qqilarining qism to‘plami bo‘lsin. Cho‘qqilar bittadan qo‘shib boriladi.
Tasdiq:
da shunday ikki cho‘qqi mavjudki, dagi istalgan cho‘qqi uchun:
Ya’ni to‘plam diametri har doim cho‘qqilar jufti bilan aniqlanadi.
Yangi cho‘qqi qo‘shilganda tekshirish kifoya:
Va zarurat bo‘lsa juftini yangilash.
Bu xossa quyidagi masalalarda ishlatiladi:
void dfs(int x, int p) {
for (int y: v[x]) {
if (y == p) {
continue;
}
dfs(y, x);
down[x] = max(down[x], down[y] + 1);
}
}
void dfs2(int x, int p) {
vector<pair<int, int>> g;
/*
We can change this logic to linear by
keeping two furthest only
*/
for (int y: v[x]) {
if (y == p) {
continue;
}
g.push_back({down[y] + 1, y}); // distance to x
}
g.push_back({0, -1});
sort(g.rbegin(), g.rend());
for (int y: v[x]) {
if (y == p) {
continue;
}
up[y] = up[x] + 1;
if (g[0].second == y) {
up[y] = max(up[y], g[1].first + 1);
} else {
up[y] = max(up[y], g[0].first + 1);
}
dfs2(y, x);
}
}