You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.
Dismiss alert
int table[Max][22]; // sparse table. there will be n rows for n nodes and logn columns for every node. pre-processing complexity O(nlogn) and Query complexity logn. table[i][j] holds 2^j th parent of ith node.
int parent[Max];
vector <int> adj[Max];
void dfs(int from, int u, int dep) {
parent[u] = from;
depth[u] = dep;
for(int i = 0; i < (int)adj[u].size(); i++) {
int v = adj[u][i];
if(v == from) continue;
dfs(u, v, dep + 1);
}
}
void lcaInit(int N) {
memset(table, -1, sizeof table);
for(int i = 0; i < N; i++) {
table[i][0] = parent[i];
}
for (int j = 1; (1 << j) < N; j++) {
for(int i = 0; i < N; i++) {
if (table[i][j - 1] != -1) {
table[i][j] = table[table[i][j - 1]][j - 1];
}
}
}
}
int lcaQuery(int p, int q) {
if(depth[p] < depth[q]) {
swap(p, q);
}
// building log's value
int log = 1;
while(true) {
int next = log + 1;
if((1 << next) > depth[p]) break;
log++;
}
// uplifting p at the same level of q
for(int i = log; i >= 0; i--) {
if (depth[p] - (1 << i) >= depth[q]) {
p = table[p][i];
}
}
if (p == q) return p;
// uplifting p and q untill both of their parents are same and we're in root
for(int i = log; i >= 0; i--) {
if (table[p][i] != -1 and table[p][i] != table[q][i]) {
p = table[p][i];
q = table[q][i];
}
}
// when p and q are in the same level, return one of their parent