Хүнд-хөнгөн задаргаа¶
Хүнд-хөнгөн задаргаа гэдэг нь мод дээрх асуулга руу шилждэг олон бодлогыг үр дүнтэй бодох боломж олгодог нэлээд ерөнхий арга техник юм.
Тайлбар¶
$n$ оройтой, дурын үндэстэй мод $G$ байг.
Энэ модны задаргааны мөн чанар нь дурын $v$-ээс хамгийн ихдээ $\log n$ замыг туулж үндэс орой хүрч болохоор модыг хэд хэдэн зам болгон хуваах явдал юм. Түүнчлэн эдгээр замын аль нь ч бусадтай огтлолцох ёсгүй.
Хэрэв бид дурын модны хувьд ийм задаргааг олбол энэ нь “$a$-ээс $b$ хүрэх зам дээр ямар нэг зүйл тооцоол” хэлбэрийн тодорхой ганц асуулгыг ”$k$ дахь замын $[l, r]$ хэрчим дээр ямар нэг зүйл тооцоол” төрлийн хэд хэдэн асуулга болгон бууруулах боломж олгоно гэдэг нь тодорхой.
Байгуулах алгоритм¶
Бид орой $v$ бүрийн хувьд түүний дэд модны хэмжээ $s(v)$-г, өөрөөр хэлбэл орой $v$-ийн дэд мод дахь өөрийг нь оруулаад оройн тоог тооцоолно.
Дараа нь орой $v$-ийн хүүхдүүд рүү очих бүх ирмэгийг авч үзье. Хэрэв ирмэг дараах нөхцөлийг хангах орой $c$ руу очиж байвал бид түүнийг хүнд гэж нэрлэнэ:
Бусад бүх ирмэгийг хөнгөн гэж шошголно.
Нэг оройноос доошоо хамгийн ихдээ нэг хүнд ирмэг гарч чадах нь илэрхий, учир нь эс бөгөөс орой $v$ нь $\ge \frac{s(v)}{2}$ хэмжээтэй дор хаяж хоёр хүүхэдтэй байх ба тиймээс $v$-ийн дэд модны хэмжээ хэт том, $s(v) \ge 1 + 2 \frac{s(v)}{2} > s(v)$ болох ба энэ нь зөрчилд хүргэнэ.
Одоо бид модыг огтлолцолгүй замууд болгон задална. Хүнд ирмэг доошоо гарахгүй байгаа бүх оройг авч үзье. Бид ийм орой бүрээс модны үндэс хүрэх эсвэл хөнгөн ирмэгээр өнгөрөх хүртэл дээшээ явна. Үр дүнд нь бид тэг буюу түүнээс олон хүнд ирмэг дээр нэмээд нэг хөнгөн ирмэгээс бүрдэх хэд хэдэн зам авна. Үндэст төгсгөлтэй зам үүнд үл хамаарах бөгөөд хөнгөн ирмэггүй байна. Эдгээрийг хүнд зам гэж нэрлэе — эдгээр нь хүнд-хөнгөн задаргааны хайж буй замууд юм.
Зөв байдлын баталгаа¶
Эхлээд алгоритмаар олдсон хүнд замууд огтлолцолгүй байх болно гэдгийг тэмдэглэе. Үнэндээ хэрэв ийм хоёр зам нийтлэг ирмэгтэй бол энэ нь нэг оройноос хоёр хүнд ирмэг гарч байна гэсэн үг болох ба энэ нь боломжгүй.
Хоёрдугаарт модны үндэснээс дурын орой хүртэл доошоо явахад бид замын дагуу $\log n$-ээс олонгүй хүнд зам солино гэдгийг харуулъя. Хөнгөн ирмэгээр доошоо шилжих нь одоогийн дэд модны хэмжээг хагас буюу түүнээс бага болгон бууруулна:
Ингэснээр дэд модны хэмжээ нэг болж багасахаас өмнө бид хамгийн ихдээ $\log n$ хөнгөн ирмэгээр өнгөрч чадна.
Бид нэг хүнд замаас нөгөө рүү зөвхөн хөнгөн ирмэгээр шилжиж чадах тул (үндэснээс эхэлдгээс бусад хүнд зам бүр нэг хөнгөн ирмэгтэй) үндэснээс дурын орой хүрэх замын дагуу бид хүнд замыг $\log n$ удаагаас олон солиж чадахгүй, шаардлагатай ёсоор.
Дараах зураг жишээ модны задаргааг үзүүлж байна. Хүнд ирмэгүүд хөнгөн ирмэгүүдээс бүдүүн. Хүнд замуудыг тасархай хүрээгээр тэмдэглэсэн.
Жишээ бодлогууд¶
Бодлого бодохдоо заримдаа хүнд-хөнгөн задаргааг (ирмэгээрээ огтлолцолгүй замуудын оронд) оройгоороо огтлолцолгүй замуудын багц гэж үзэх нь илүү тохиромжтой байдаг. Үүнийг хийхийн тулд хүнд зам бүрээс сүүлийн ирмэгийг, хэрэв тэр нь хөнгөн ирмэг бол хасахад хангалттай, тэгвэл ямар ч шинж чанар зөрчигдөхгүй боловч одоо орой бүр яг нэг хүнд замд харьяалагдана.
Доор бид хүнд-хөнгөн задаргааны тусламжтайгаар бодож болох зарим ердийн даалгаврыг авч үзнэ.
Тусад нь зам дээрх тоонуудын нийлбэр-ийн бодлогод анхаарал хандуулах нь зүйтэй, учир нь энэ нь илүү энгийн арга техникээр бодож болох бодлогын жишээ юм.
Хоёр оройн хоорондох зам дээрх хамгийн их утга¶
Мод өгөгдсөн, орой бүрд утга оноогдсон. $(a, b)$ хэлбэрийн асуулгууд байх ба энд $a$ ба $b$ нь модны хоёр орой бөгөөд орой $a$ ба $b$-ийн хоорондох зам дээрх хамгийн их утгыг олох шаардлагатай.
Бид урьдчилан модны хүнд-хөнгөн задаргааг байгуулна. Хүнд зам бүр дээр бид Хэрчмийн мод байгуулах ба энэ нь заасан хүнд замын заасан хэрчимд хамгийн их оноосон утгатай оройг $\mathcal{O}(\log n)$-д хайх боломж олгоно. Хэдийгээр хүнд-хөнгөн задаргаа дахь хүнд замын тоо $n - 1$ хүрч болох ч бүх замын нийт хэмжээ $\mathcal{O}(n)$-ээр хязгаарлагдах тул Хэрчмийн модуудын нийт хэмжээ мөн шугаман байна.
$(a, b)$ асуулгад хариулахын тулд бид дуртай аргаараа $a$ ба $b$-ийн хамгийн бага нийтлэг өвөг-ийг $l$ гэж олно. Одоо даалгавар $(a, l)$ ба $(b, l)$ гэсэн хоёр асуулга болж буурсан бөгөөд тэдгээрийн тус бүрийн хувьд бид дараахыг хийж болно: доод орой байрлаж буй хүнд замыг олж, энэ зам дээр асуулга хийж, энэ замын оройд шилжиж, дахин аль хүнд зам дээр байгаагаа тодорхойлж, түүн дээр асуулга хийх гэх мэтчилэн $l$-г агуулсан замд хүрэх хүртэл.
Жишээ нь $a$ ба $l$ нэг хүнд зам дээр байх тохиолдолд болгоомжтой байх хэрэгтэй — тэгвэл энэ зам дээрх максимумын асуулгыг дурын угтвар дээр биш $a$ ба $l$-ийн хоорондох дотоод хэсэг дээр хийх ёстой.
$(a, l)$ ба $(b, l)$ дэд асуулгад хариулах тус бүр нь $\mathcal{O}(\log n)$ хүнд замаар өнгөрөх шаардлагатай бөгөөд зам бүрийн хувьд замын ямар нэг хэсэг дээр максимумын асуулга хийгддэг ба энэ нь дахин Хэрчмийн модонд $\mathcal{O}(\log n)$ үйлдэл шаардана. Тиймээс нэг асуулга $(a, b)$ нь $\mathcal{O}(\log^2 n)$ хугацаа авна.
Хэрэв та нэмж хүнд зам бүрийн хувьд бүх угтварын максимумыг тооцоолж хадгалбал $\mathcal{O}(\log n)$ шийд авна, учир нь бид өвөг $l$ хүрэх үеийн хамгийн ихдээ нэг удаагаас бусад бүх максимумын асуулга угтвар дээр байна.
Хоёр оройн хоорондох зам дээрх тоонуудын нийлбэр¶
Мод өгөгдсөн, орой бүрд утга оноогдсон. $(a, b)$ хэлбэрийн асуулгууд байх ба энд $a$ ба $b$ нь модны хоёр орой бөгөөд орой $a$ ба $b$-ийн хоорондох зам дээрх утгуудын нийлбэрийг олох шаардлагатай. Нэг буюу хэд хэдэн оройд оноосон тоог өөрчлөх шинэчлэх үйлдэл нэмж байх энэ даалгаврын хувилбар байж болно.
Энэ даалгаврыг хүнд замууд дээр Хэрчмийн мод байгуулах замаар хүнд-хөнгөн задаргааны тусламжтайгаар өмнөх максимумын бодлоготой адилаар бодож болно. Хэрэв шинэчлэл байхгүй бол оронд нь угтвар нийлбэр ашиглаж болно. Гэвч энэ бодлогыг илүү энгийн арга техникээр ч бодож болно.
Хэрэв шинэчлэл байхгүй бол хоёр оройн хоорондох зам дээрх нийлбэрийг хоёртын өргөлт-өөр хоёр оройн LCA хайлттай зэрэгцүүлэн олох боломжтой — үүний тулд урьдчилсан боловсруулалтын явцад орой бүрийн $2^k$-р өвгүүдийн хамт тэдгээр өвөг хүрэх зам дээрх нийлбэрийг мөн хадгалах шаардлагатай.
Энэ бодлогод үндсэндээ өөр хандлага бий — модны Эйлерийн тойролт-ыг авч үзээд, түүн дээр Хэрчмийн мод байгуулах. Энэ алгоритмыг ижил төстэй бодлогын тухай өгүүлэлд авч үзсэн. Дахин хэлэхэд шинэчлэл байхгүй бол угтвар нийлбэр хадгалах нь хангалттай бөгөөд Хэрчмийн мод шаардлагагүй.
Эдгээр хоёр арга хоёулаа нэг асуулгад $\mathcal{O}(\log n)$ авах харьцангуй энгийн шийдийг өгнө.
Хоёр оройн хоорондох замын ирмэгүүдийг дахин будах¶
Мод өгөгдсөн, ирмэг бүр анх цагаанаар будагдсан. $(a, b, c)$ хэлбэрийн шинэчлэлүүд байх ба энд $a$ ба $b$ нь хоёр орой, $c$ нь өнгө бөгөөд $a$-ээс $b$ хүрэх зам дээрх бүх ирмэгийг өнгө $c$-ээр дахин будах ёстойг заана. Бүх дахин будалтын дараа өнгө бүрийн хэдэн ирмэг гарсныг мэдээлэх шаардлагатай.
Дээрх бодлогуудтай адилаар шийд нь зүгээр л хүнд-хөнгөн задаргааг хэрэглэж, хүнд зам бүр дээр Хэрчмийн мод байгуулах явдал юм.
$(a, b)$ зам дээрх дахин будалт бүр $(a, l)$ ба $(b, l)$ гэсэн хоёр шинэчлэл болж хувирна, энд $l$ нь орой $a$ ба $b$-ийн хамгийн бага нийтлэг өвөг юм.
$\mathcal{O}(\log n)$ зам бүрд $\mathcal{O}(\log n)$ нь шинэчлэл бүрд $\mathcal{O}(\log^2 n)$ complexity-д хүргэнэ.
Implementation¶
Certain parts of the above discussed approach can be modified to make implementation easier without losing efficiency.
- The definition of heavy edge can be changed to the edge leading to the child with largest subtree, with ties broken arbitrarily. This may result is some light edges being converted to heavy, which means some heavy paths will combine to form a single path, but all heavy paths will remain disjoint. It is also still guaranteed that going down a light edge reduces subtree size to half or less.
- Instead of a building segment tree over every heavy path, a single segment tree can be used with disjoint segments allocated to each heavy path.
- It has been mentioned that answering queries requires calculation of the LCA. While LCA can be calculated separately, it is also possible to integrate LCA calculation in the process of answering queries.
To perform heavy-light decomposition:
vector<int> parent, depth, heavy, head, pos;
int cur_pos;
int dfs(int v, vector<vector<int>> const& adj) {
int size = 1;
int max_c_size = 0;
for (int c : adj[v]) {
if (c != parent[v]) {
parent[c] = v, depth[c] = depth[v] + 1;
int c_size = dfs(c, adj);
size += c_size;
if (c_size > max_c_size)
max_c_size = c_size, heavy[v] = c;
}
}
return size;
}
void decompose(int v, int h, vector<vector<int>> const& adj) {
head[v] = h, pos[v] = cur_pos++;
if (heavy[v] != -1)
decompose(heavy[v], h, adj);
for (int c : adj[v]) {
if (c != parent[v] && c != heavy[v])
decompose(c, c, adj);
}
}
void init(vector<vector<int>> const& adj) {
int n = adj.size();
parent = vector<int>(n);
depth = vector<int>(n);
heavy = vector<int>(n, -1);
head = vector<int>(n);
pos = vector<int>(n);
cur_pos = 0;
dfs(0, adj);
decompose(0, 0, adj);
}
The adjacency list of the tree must be passed to the init function, and decomposition is performed assuming vertex 0 as root.
The dfs function is used to calculate heavy[v], the child at the other end of the heavy edge from v, for every vertex v. Additionally dfs also stores the parent and depth of each vertex, which will be useful later during queries.
The decompose function assigns for each vertex v the values head[v] and pos[v], which are respectively the head of the heavy path v belongs to and the position of v on the single segment tree that covers all vertices.
To answer queries on paths, for example the maximum query discussed, we can do something like this:
int query(int a, int b) {
int res = 0;
for (; head[a] != head[b]; b = parent[head[b]]) {
if (depth[head[a]] > depth[head[b]])
swap(a, b);
int cur_heavy_path_max = segment_tree_query(pos[head[b]], pos[b]);
res = max(res, cur_heavy_path_max);
}
if (depth[a] > depth[b])
swap(a, b);
int last_heavy_path_max = segment_tree_query(pos[a], pos[b]);
res = max(res, last_heavy_path_max);
return res;
}