Eng kichik umumiy ajdod
Ildizli daraxt berilgan bo‘lsin.
Ikki cho‘qqi va ning eng kichik umumiy ajdodi — bu ham ning, ham ning ajdodi bo‘ladigan eng chuqur cho‘qqidir.
Sodda qilib aytganda: agar va dan ildizga qarab yuqoriga ko‘tarilsak, LCA — ularning yo‘llari birinchi marta kesishadigan cho‘qqidir.
Biz quyidagilarni faraz qilamiz:
Agar ning ajdodi bo‘lsa, unda javob — .
Aks holda ni yuqoriga ko‘taramiz.
G‘oya:
biz ni imkon qadar yuqoriga ko‘tarishni xohlaymiz, lekin ning ajdodi bo‘lib qoladigan cho‘qqiga kirib ketmaslik kerak.
Buning uchun katta uzunlikdagi sakrashlarni sinab ko‘ramiz (binar ko‘tarilishdagidek):
Natijada biz cho‘qqisiga kelamiz, u deyarli LCA, lekin o‘zi hali ning ajdodi emas.
Unda uning ota-cho‘qqisi javob bo‘ladi.
Bu usul odatda tushunarliroq deb hisoblanadi va amaliyotda ko‘proq qo‘llaniladi.
Endi ikkala cho‘qqi ham bir xil chuqurlikda joylashgan.
Agar chuqurliklarni tenglashtirgandan keyin bo‘lib chiqsa, demak bu LCA — ni qaytaramiz.
Agar bo‘lsa, demak LCA yuqoriroqda joylashgan.
Ikkala cho‘qqini bir vaqtda ko‘taramiz, eng katta sakrashlardan boshlab:
Katta sakrashlardan kichiklariga o‘tamiz.
Oxirida va LCA ning bevosita ostida bo‘ladi. Javob — ularning bevosita ota-cho‘qqisi:
int lca(int x, int y) {
if (isParent(x, y)) {
return x;
}
for (int i = L; i >= 0; i--) {
if (!isParent(par[x][i], y)) {
x = par[x][i];
}
}
return par[x][0];
}
int lca(int x, int y) {
if (dip[x] > dip[y]) {
swap(x, y);
}
// y ni x chuqurligigacha ko‘taramiz
y = jump(y, dip[y] - dip[x]);
if (x == y) {
return x;
}
for (int i = L; i >= 0; i--) {
if (par[x][i] != par[y][i]) {
x = par[x][i];
y = par[y][i];
}
}
return par[x][0];
}