Tree-ийн хоёр node-ын хамгийн ойрын нийтлэг өвгийг 2^j алхмаар үсэрч O(log n) хугацаанд олно.

Advanced & LegendХугацаа: O(n log n + q log n)Санах ой: O(n log n)

Эхлээд жижиг бодлого

Root нь 1. 2, 3, …, 10 node-ын parent нь 1, 1, 2, 2, 3, 4, 4, 7, 6. 9, 5 хоёрын хамгийн ойрын нийтлэг өвөг хэн бэ?

9 → 7 → 4 → 2 → 1, 5 → 2 → 1. Хоёулаа анх 2-т таарна. Хариу: 2. Харин 8, 10 хоёрынх 1.

Энгийн аргаас санаа руу

Энгийн арга: гүнийг тэнцүүлээд, хоёуланг нь нэг нэг алхмаар дээшлүүлж, таартал явна. Нэг query-д O(n). Гинж хэлбэртэй tree дээр 10⁵ query-д 10¹⁰ алхам хүрнэ.

Гол санаа: нэг нэг биш 2^j алхмаар үсэрнэ. up[j][i]-г урьдчилан бодвол дурын алхмын тоог хоёртын задаргаагаар нь log n үсрэлтэд хийнэ. LCA-г олохдоо LCA-гаас дээш гарахгүйгээр аль болох том үсрэлт хийнэ.

Нэр томьёо ба тэмдэглэгээ

up[j][i]
i-гаас 2^j алхам дээш гарахад хүрэх node. up[0][i] нь parent.
dep[i]
i-н гүн: root-ээс i хүртэлх edge-ийн тоо.
LOG
2^LOG ≥ n байх хамгийн бага тоо. Хүснэгт LOG мөртэй.
LCA
Lowest Common Ancestor: хоёр node-ын хамгийн ойрын нийтлэг өвөг.
1гүн 02гүн 13гүн 14гүн 25гүн 26гүн 27гүн 38гүн 39гүн 410гүн 3
LOG = 4
up[0] (1 алхам)
1→12→13→14→25→26→37→48→49→710→6

Tree: 10 node-той, root нь 1. up[0] мөрөнд node бүрийн parent бий. Одоо up[j][i] буюу i-гаас 2^j алхам дээш гарахад хүрэх node-ыг бөглөнө.

Алхам 1 / 37
Хурд
  • i эсвэл u
  • Дундах node эсвэл v
  • Хүрсэн node эсвэл хариу
Слайд 1 / 6

Нийтлэг өвөг

Ургийн модонд хоёр хүний хамгийн ойрын нийтлэг өвөг хэн бэ? Tree дээр үүнийг LCA гэнэ. Нэг нэг алхмаар дээшилбэл удаан. Binary Lifting 2^j алхмаар үсэрдэг.

lca-binary-lifting.cpp
#include <bits/stdc++.h>
using namespace std;
int n, q, LOG, u, v, dep[100005], up[17][100005];
int main() {
cin >> n >> q;
up[0][1] = 1;
for (int i = 2; i <= n; i++) {
cin >> up[0][i];
dep[i] = dep[up[0][i]] + 1;
}
while ((1 << LOG) < n) LOG++;
for (int j = 1; j < LOG; j++) {
for (int i = 1; i <= n; i++) {
up[j][i] = up[j - 1][up[j - 1][i]];
}
}
while (q--) {
cin >> u >> v;
if (dep[u] < dep[v]) swap(u, v);
for (int j = LOG - 1; j >= 0; j--) {
if (dep[u] - (1 << j) >= dep[v]) {
u = up[j][u];
}
}
if (u == v) {
cout << u << '\n';
continue;
}
for (int j = LOG - 1; j >= 0; j--) {
if (up[j][u] != up[j][v]) {
u = up[j][u];
v = up[j][v];
}
}
cout << up[0][u] << '\n';
}
return 0;
}

Юунд хэрэгтэй вэ?

Tree-ийн хоёр node-ын хамгийн ойрын нийтлэг өвөг (LCA) олох query-д хурдан хариулна. Tree дээрх хоёр node-ын зай, path-ын нийлбэр зэрэг олон бодлогын суурь.

Яаж ажилладаг вэ?

1. up[j][i] бол i-гаас 2^j алхам дээш гарахад хүрэх node. up[0][i] нь parent, root-ийн parent нь root өөрөө. 2. Бөглөх: 2^j алхам = 2^(j − 1) алхам, дахиад 2^(j − 1) алхам. Тэгэхээр up[j][i] = up[j − 1][up[j − 1][i]]. 3. Query: u гүн талд нь байхаар u, v-г сольно. Гүний зөрүүг том үсрэлтээс нь эхлэн задалж, u-г v-гийн гүн хүртэл өргөнө. 4. u = v бол тэр л хариу. Үгүй бол j-г томоос нь бууруулж, up[j][u] ≠ up[j][v] үед хоёуланг нь үсрүүлнэ. 5. Төгсгөлд u, v хоёр нэг parent-тэй болно: хариу нь up[0][u]. Оролт: эхний мөрөнд n ба q, дараагийн мөрөнд 2, 3, …, n node-ын parent (өөрөөсөө бага дугаартай, root нь 1), дараа нь q мөр "u v".

Яагаад зөв, хэр хурдан бэ?

Гүнийг тэнцүүлэхдээ зөрүүг хоёртын тоогоор задалж, 1 бит бүрт нэг үсэрнэ. Дараа нь j-г томоос нь бууруулж, up[j][u] ≠ up[j][v] үед л үсэрнэ. Ингэхэд u, v үргэлж LCA-гаас доор үлдэж, үсэрч болох хамгийн дээд цэгт хүрнэ. Тэр цэгийн parent нь LCA.

Хүснэгт бөглөх O(n log n), query бүр O(log n). n = 10⁵ бол LOG = 17, query бүр 34 орчим үсрэлт.

Түгээмэл алдаа

  • Root-ийн parent-ийг 0 болгох. Тэгвэл up[j][i] 0 рүү үсэрч, буруу хариу өгнө. Root-ийн parent нь root өөрөө.
  • Гүнийг тэнцүүлсний дараа u == v эсэхийг шалгахаа мартах. Нэг нь нөгөөгийнхөө өвөг бол хариу нь тэр өөрөө.
  • Хоёр дахь loop-д j-г бага утгаас нь эхлүүлэх. Том үсрэлтээс эхлэх ёстой.
  • Эцэст нь u-г хэвлэх. Хариу нь u биш, up[0][u].

Хязгаарын тохиолдол

  • u = v: гүн ижил, шууд хариу u.
  • Нэг нь нөгөөгийнхөө өвөг: гүнийг тэнцүүлэхэд хоёулаа нэг node-д ирнэ, тэр нь хариу.
  • Гинж хэлбэртэй tree: гүн n − 1 хүрнэ, гэхдээ үсрэлт log n хэвээр.
  • Од хэлбэртэй tree: root-ээс бусад хоёр өөр node-ын LCA үргэлж root.

Өөрийгөө шалга

  1. Жишээ tree-д 7-гоос 2 алхам дээш гарвал хаана очих вэ?

    Хариу харах

    2. up[1][7] = 2: 7 → 4 → 2.

  2. n = 1000 бол LOG хэд вэ?

    Хариу харах

    10. 2^10 = 1024 ≥ 1000.

  3. Жишээ tree-д 8, 9 хоёрын LCA хэд вэ?

    Хариу харах

    4. 9 → 7 → 4, 8 → 4.

Гурван дадлага

Hint-ээ нээхээс өмнө өөрөө оролдоорой.

  1. 1.Жишээ tree-д 10, 5 хоёрын LCA-г гараар ол. Үсрэлт бүрийг бич.

    Hint харах

    10-ын гүн 3, 5-ын гүн 2.

    Хариу ба тайлбар

    Гүнийг тэнцүүлэхэд u = 10 нэг алхам өгсөж 6 болно. Дараа нь j = 0 дээр 3 ≠ 2 тул u = 3, v = 2. Хариу нь тэдний parent: 1.

  2. 2.Хоёр node-ын хоорондох зайг, өөрөөр хэлбэл edge-ийн тоог ол.

    Hint харах

    dep ба LCA ашигла.

    Хариу ба тайлбар

    Зай = dep[u] + dep[v] - 2 * dep[lca].

  3. 3.u-гаас k алхам дээш гарахад хүрэх node-ыг O(log n) хугацаанд ол.

    Hint харах

    k-г хоёртоор бич.

    Хариу ба тайлбар

    for (int j = 0; j < LOG; j++) if (k >> j & 1) u = up[j][u]; k нь u-гийн гүнээс их бол root-д хүрнэ.

Жишээ

Оролт

10 2
1 1 2 2 3 4 4 7 6
9 5
8 10

Гаралт

2
1