|
Farak-Kolton va Bender algoritmi yordamida eng kichik umumiy ajdodni toppish
Daraxt - bu N ta burchak va N-1 qirralarning yoʻnaltirilmagan bogʻlangan grafigi. Har qanday uch boshqasiga bitta oddiy yo'l bor.Daraxtning ildizi shunday uch deb ataladi, undan o'tayotganda daraxt bo'ylab harakat yo'nalishi aniqlanadi.Ikki u va v uchlarning eng kichik umumiy ajdodi ildizdan v uchga va u uch bo'lgan yo'lda yotuvchi p uch, shuningdek, undan maksimal masofadir.
Kirish daraxt haqidagi ma'lumotni oladi: N - uchlari soni, N-1 - chekka bilan bog'langan juft uchlari va M - so'rovlar soni. Keyinchalik, dastur so'rovlarni qabul qiladi: ikkita u va v uchlari, buning uchun ularning eng kichik umumiy ajdodini topish talab qilinadi.
Algoritm g'oyasi
Biz har bir cho'qqi uchun ildizgacha bo'lgan masofani va biz unga kelgan oldingi cho'qqiga (ajdod) saqlaymiz. Keyin u va v cho'qqilaridan daraxtning ildizigacha ko'tarilamiz. Har bir qadamda biz ildizdan eng uzoq bo'lgan u yoki v cho'qqisini tanlaymiz, so'ngra uning o'rniga uning ajdodini ko'rib chiqamiz, toki boshlang'ich u va v dan hosil bo'lgan yo'llar bitta cho'qqiga - ularning eng kichik umumiy ajdodiga olib borguncha. Daraxtning turli xil variantlari bilan bunday yo'l N qadamdan iborat bo'lishi mumkin, bu juda ko'p sonli tepaliklar va so'rovlar bilan juda sekin ishlaydi. Ushbu dastur har bir so'rovni bajarish uchun O(N) vaqtini oladi.
Endi algoritmni yaxshilaymiz. Har bir cho'qqi uchun biz daraxtning ildizigacha bo'lgan masofani, uning bolalari borligini, shuningdek, biz oxirgi marta kelgan ajdodni (tanlash quyida aniqlanadi) va sonini saqlaymiz. qirrasi ajdoddan bu cho'qqiga burilish yo'lida ketadigan cho'qqining.
Kerakli o'zgaruvchilarni e'lon qilaylik, qulaylik uchun bu global xotirada amalga oshiriladi.
const int SIZE = 100050;
vector v[SIZE]; // har bir cho'qqi uchun qirralarning ro'yxati
bool vis[SIZE]; // o'tish paytida tepaliklarga tashrif buyurish haqida bayroqlarint kids[SIZE]; // har bir tepalik uchun bolalar soni
int dist[SIZE]; // yuqoridan ildizgacha bo'lgan masofa
int last[SIZE]; // oldingi cho'qqi raqami
int turn[SIZE];
Endi, har bir cho'qqi uchun rekursiv funktsiyadan foydalanib (k_go (0) chaqiring) biz uning avlodlari sonini hisoblaymiz:
int k_go(int s) {
int res = 0; vis[s] = true;
for(int i = 0, maxi = v[s].size(); i < maxi; i++) {
if(!vis[v[s][i]]) res += k_go(v[s][i]) + 1;
}
kids[s] = res; return res;
}
Va endi algoritmning tayyorgarlik qismini tugatamiz va har bir cho'qqi uchun kerakli ma'lumotlarni to'ldiramiz. Biz l_go(0, 0, 0, 1) funksiyasini chaqiramiz:
void l_go(int s, int d, int l, int r) {
vis[s] = true;
dist[s] = d; last[s] = l; turn[s] = r;
int maxval = 0; int idx = -1;
for(int i = 0, maxi = v[s].size(); i < maxi; i++) {
if(!vis[v[s][i]]) {
int k = kids[v[s][i]];
if(k > maxval) idx = v[s][i], maxval = k;
} }
for(int i = 0, maxi = v[s].size(); i < maxi; i++) {
if(!vis[v[s][i]]) { if(idx == v[s][i])
l_go(v[s][i], d + 1, l, r);
else
l_go(v[s][i], d + 1, s, v[s][i]);
}}}
Endi men kodning oxirgi qismi qanday ishlashini tushuntiraman, chunki tepadagi bolalar sonini topish juda odatiy vazifadir.
Har bir cho'qqi uchun biz uning avlodlarini ko'rib chiqamiz va ular orasidan avlodlar soni maksimal bo'lgan cho'qqini tanlaymiz. Buning uchun ajdod haqidagi barcha ma'lumotlar hozirgisidan meros bo'lib qoladi va faqat ildizgacha bo'lgan masofa o'zgaradi. Ushbu cho'qqining barcha boshqa avlodlari uchun oxirgining ajdodi hozirgi cho'qqi bo'ladi va burilish bolaning o'zini aylantiradi.
Endi men da'vo qilamanki, agar biz daraxtda qandaydir a cho'qqisini olsak va undan ildizga kelgunimizcha, oxirgi ajdodga o'tishlar soni daraxtdagi cho'qqilar sonining ikkilik logarifmasidan oshmaydi.
Isbot: deylik, biz bitta bolaga ega bo'lgan v cho'qqisida turibmiz. Shunda undan qolgan avlodning ajdodiga nisbatan oxirgining ishorasi o'zgarmasligi aniq. Ikki yoki undan ortiq cho'qqilar bo'lsa, biz bitta avlodni olamiz (joriy cho'qqining barcha avlodlari orasida eng ko'p avlodga ega), uning aloqasi hozirgi va qolgan barchadan meros bo'lib o'tadi. yangilanadi. Joriy cho'qqi avlodlarining umumiy sonini N deb belgilaymiz. Keyin bu cho'qqining avlodidan, buning uchun ajdodga havolani yangilaymiz, N/2 avloddan ko'p bo'lmaydi (aks holda bu son bo'ladi maksimal, lekin keyin havolani yangilash shart emas). Shunday qilib, oxirgisining ajdodi bo'lgan cho'qqilarning har birida birov uchun, undan keladigan barcha avlodlardan yarmidan ko'pi qolmaydi. Bunday yo'lning umumiy uzunligi N ning ikkilik logarifmasidan oshmaydi.
Endi algoritmning asosiy funktsiyasiga o'tamiz va nima uchun ishlashini tushuntiramiz.
Shunday qilib, bizda ikkita u va v uchlari bor, ular uchun so'rovga javob topishimiz kerak. Funksiyani p = lca(u, v) deb ataylik:
int lca(int a, int b) {
if(turn[a] == turn[b]) {
if(dist[a] < dist[b]) return a; else return b; }
if(dist[last[a]] > dist[last[b]]) return lca(last[a], b);
return lca(last[b], a);
}
Funktsiya rekursiv ravishda ildiz tomon ko'tariladi. Har bir keyingi a va b cho'qqilari uchun birinchi navbatda oxirgi aylanish amalga oshirilgan cho'qqini tekshiramiz. Agar u mos kelsa, demak, a cho'qqisi ildizdan b cho'qqigacha bo'lgan yo'lda yotadi yoki aksincha. Qaysi cho'qqi ildizga yaqinroq ekanligiga qarab, u eng kam umumiy ajdod hisoblanadi.
Aks holda, a yoki b cho'qqisini ildizga yaqinlashtirish kerak. Biz ularning qaysi biri ajdodiga o'tgan taqdirda, ildizdan uzoqroqda bo'lishini taxmin qilamiz (bir cho'qqi doimiy ravishda ildizga boradigan yo'lda ikkinchi cho'qqiga yetib borishga harakat qiladi). Shunday qilib, ertami-kechmi cho'qqilar bitta cho'qqiga etib boradi, bu darhol ularning eng kichik umumiy ajdodi bo'ladi yoki cho'qqilardan biri birinchi bosqichda tasvirlangan ildizdan boshqa cho'qqigacha bo'lgan yo'lda yotadi.
Do'stlaringiz bilan baham: |
