Падари умумии хурдтарин
Бигзор дарахте бо реша дода шуда бошад.
Аҷдоди умумии хурдтарин-и ду қуллаи ва — ин амиқтарин қуллаест, ки ҳам барои , ҳам барои аҷдод мебошад.
Ба таври содда: агар аз ва ба боло ба сӯи реша равем, пас LCA — ин аввалин қуллаест, ки роҳҳои онҳо дар он бурида мешаванд.
Мо фарз мекунем, ки:
Агар аҷдоди бошад, пас ҷавоб — аст.
Вагарна -ро ба боло мебардорем.
Ғоя:
мо мехоҳем -ро то ҳадди имкон боло бардорем, аммо ба қуллае надароем, ки аллакай аҷдоди мебошад.
Барои ин ҷаҳишҳои дарозии калонро месанҷем (мисли бардоштани бинарӣ):
Дар натиҷа мо дар қуллаи қарор мегирем, ки аллакай қариб LCA аст, аммо худ ҳанӯз аҷдоди нест.
Пас падари он ҷавоб мешавад.
Ин роҳ одатан фаҳмотар ҳисобида мешавад ва бештар дар амал истифода мешавад.
Акнун ҳар ду қулла дар як амиқӣ қарор доранд.
Агар баъд аз баробар кардани амиқиҳо маълум шавад, ки , пас ин ҳамон LCA аст — -ро бармегардонем.
Агар , пас LCA болотар ҷойгир аст.
Ҳар ду қулларо ҳамзамон мебардорем, аз ҷаҳишҳои калонтарин оғоз карда:
Аз ҷаҳишҳои калон ба хурд меравем.
Дар охир ва рост дар зери LCA қарор мегиранд. Ҷавоб — падари бевоситаи онҳо аст:
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-ро то амиқии x мебардорем
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];
}