def find(u, v): # تابع پیدا کردن LCA به همراه محاسبه جواب
ans = 0
while u != v: # تا زمانی که به هم برسند
if depth[u] < depth[v]: # مطمئن شو u پایینتر است
u, v = v, u
# ...
u = parent[u]
return ans
An O(n + q*lg(n)) Solution Using Heavy-Light Decomposition¶
In this section, we present an \(O(n+q\cdot\lg(n))\) solution for the mentioned problems using heavy-light decomposition.
Heavy-Light Decomposition¶
This decomposition is a widely-used technique in trees. It divides the tree edges into two categories: heavy and light. Heavy edges are those where the size of the corresponding child subtree is larger than that of the other child edges. Only one child can have a heavy edge, and if multiple children have the maximum size, we arbitrarily choose one of their edges as heavy.
Number of Light Edges on the Path to the Root¶
The number of light edges on the path from any vertex to the root is at most \(O(\lg(n))\). This is because starting from an arbitrary vertex and moving upward toward the root, we define the variable \(X\) as the size of the subtree of the current vertex. Every time we move upward (from vertex v to u) and traverse a light edge, \(X\) at least doubles. Otherwise, \(2sz_v > sz_u\) implies that this vertex occupies more than half of its parent's subtree, meaning its edge must necessarily be heavy. Since \(X\) will ultimately equal \(n\), the maximum number of light edges is \(\lg(n)\).
Solving the Problem of Ancestor at a Specific Height¶
A vertex can have at most one heavy child. Therefore, during DFS, we first visit the vertex through its heavy edge so that the entry time of the heavy child is exactly one unit greater than its parent. This way, if we sort vertices based on their entry time, any vertex connected to its parent via a heavy edge will be positioned immediately after its parent.
Obtain this ordering, and also determine for each vertex how many of its ancestors are positioned immediately behind it in this order. In other words, find the first light edge on the path from this vertex to the root.
Now, to find an ancestor of a vertex at a specific height: If the number of ancestors positioned behind this vertex exceeds the desired height (i.e., all edges up to the target ancestor are heavy), we can retrieve the target ancestor in \(O(1)\) time. However, if a light edge exists along the path, we must climb to the ancestor connected via a light edge to its parent, then find its parent, and continue from there. Since there are at most \(O(\lg(n))\) light edges on any path from a vertex to the root, this process takes \(O(\lg(n))\) time per query. Thus, the total time complexity is \(O(n + q \cdot \lg(n))\).
#include<bits/stdc++.h>
using namespace std;
const int M = 1e5+5;
int edge_counter = 1;
int st[M], stp[M], hld[M], par[M], h[M];
vector<int> g[M];
int time = 0;
int dfsz(int x, int p = 0) {
int sz = 1, mxsz = -2;
if (p == g[x][0]) swap(g[x][0], g[x][g[x].size()-1]);
for (int i = 0; i < g[x].size(); i++) {
if (g[x][i] == p) continue;
int szy = dfsz(g[x][i], x);
sz += szy;
if (szy > mxsz) {
mxsz = szy;
swap(g[x][0], g[x][i]); // enteghale yal sangin be g[x][0]
}
}
return sz;
}
void dfst(int stpx, int p = 0) {
int x = st[stpx] = time++; // shomare ras ha ra joori avaz mikonim ke yal haye sangin
stp[x] = stpx; // motevali bashand. in jayghasht ra dar st[x] va barakse aan ra dar stp[x] mirizim
for (int stpy: g[stpx]) {
if (stpy == p) continue;
dfst(stpy, stpx);
par[st[stpy]] = x;
}
}
int parat(int stpx, int hgoal) { // jadi az rase voroodi ke ertefae hadaf ra darad ra mikhahim
int x = hld[st[stpx]];
while (h[x] > hgoal) x = hld[par[x]];
return stp[x + hgoal - h[x]];
}
int main(){
// derakht ra voroodi begirid va yal ha ra dar g berizid
dfsz(0);
dfst(0);
for (int x = 1; x < n; x++) {
h[x] = h[par[x]] + 1;
hld[x] = par[x] == x - 1 ? hld[x-1] : x; // hld[x] bala tarin jadi ast ke be aan yale sangin darim
}
// sepas porsesh ha ra ba parat pasokh dahid
}
Solving the LCA Problem¶
According to what we discussed in the previous section, the described approach provides an \(O(n+q*lg^2(n))\) solution for the Lowest Common Ancestor (LCA) problem. However, we can easily optimize this solution. Consider the lowest common ancestor. The path from one of the vertices to this ancestor must contain a light edge (both edges cannot be heavy simultaneously). Thus, we can find the LCA using the following algorithm:
Determine which vertex's light edge is lower.
Find the corresponding ancestor of the other vertex at the same height.
Compute the parent of both vertices.
If they are equal, we have found the common ancestor. Otherwise, repeat the process with the new vertices.
Since there are at most \(O(log\ n)\) light edges in any path of the tree, this algorithm achieves a time complexity of \(O(n+q*lg(n))\).
const int M = 1e5+5;
int edge_counter = 1;
int st[M], stp[M], hld[M], par[M], h[M];
vector <int> g[M];
int time = 0;
int dfsz(int x, int p = 0) {
int sz = 1, mxsz = -2;
if (p == g[x][0]) swap(g[x][0], g[x][g[x].size() - 1]);
for (int i = 0; i < g[x].size(); i++) {
if (g[x][i] == p) continue;
int szy = dfsz(g[x][i], x);
sz += szy;
if (szy > mxsz) {
mxsz = szy;
swap(g[x][0], g[x][i]); // enteghale yal sangin be g[x][0]
}
}
return sz;
}
void dfst(int stpx, int p = 0) {
int x = st[stpx] = time++; // shomare ras ha ra joori avaz mikonim ke yal haye sangin
stp[x] = stpx; // motevali bashand. in jayghasht ra dar st[x] va barakse aan ra dar stp[x] mirizim
for (int stpy: g[stpx]) {
if (stpy == p) continue;
dfst(stpy, stpx);
par[st[stpy]] = x;
}
}
int parat(int x, int hgoal) { // jadi az rase voroodi ke ertefae hadaf ra darad ra mikhahim
int x = hld[x];
while (h[x] > hgoal) x = hld[par[x]];
return x + hgoal - h[x];
}
int lca(int stpx, int stpy) {
int x = st[stpx], y = st[stpy];
if (h[x] < h[y]) swap(x,y);
x = parat(x, h[y]); // do ras ra ham ertefa mikonim ta kod sade tar shavad
while (x != y) {
x = hld[x];
y = hld[y];
if (h[x] < h[y]) swap(x, y);
y += h[x] - h[y];
x = par[x];
y = par[y];
}
return stp[x];
}
int main(){
// derakht ra voroodi begirid va yal ha ra dar g berizid
dfsz(0);
dfst(0);
for (int x = 1; x < n; x++) {
h[x] = h[par[x]] + 1;
hld[x] = par[x] == x - 1 ? hld[x-1] : x; // hld[x] bala tarin jadi ast ke be aan yale sangin darim
}
// sepas porsesh ha ra ba parat pasokh dahid
}
This book is made by The Shaazzz contributors.
It is publicly available with cc-by-sa license.
Last updated at آوریل 19, 2025.
Rendered by Sphinx (4.3.2) and Minoo theme (Beta 0.9.7).
