Algorithm
In binary lifting, we pre-compute the ancestors of the node whose distance is \(\lbrace 2^i \,| \, 0 \le i \le \log(n) \rbrace\), n is number of nodes in the graph. Given this table, we can find lca between two nodes u and v in \(\mathcal{O}(\log(n)).\)
Table Computation:
Given this table and assume we have information about their ancestors for all nodes up to \(2^{i}\). To find the ancestor at 2^{i+1} we just have to perform two jumps of distance \(2*2^{i}\). The computation of the table is \(\mathcal{O}(n\log(n))\).
Find the ancestor that is k distance away from it.
Leave it you as an exercise. Hint: It can be found in \(\mathcal{O}(\log(n))\).
Problems
- https://open.kattis.com/problems/tourists
- http://codeforces.com/problemset/problem/519/E
- https://www.codechef.com/problems/POSTTREE
- https://www.codechef.com/problems/DRAGONST
Solutions
Problem A - Tourists
//
// Created by Nivin Anton Alexis lawrence on 2/22/18.
// Binary Lifting, LCA, DP
//
#include <iostream>
#include <vector>
#include <queue>
#define ll long long
#define MAXN 2000005
#define LOGMAXN 19
/* vertex index starts from 1...n */
//find the last bit and subtract -1 to it.., understanding the jump and the size will be helpful..
int table[LOGMAXN + 4][MAXN], visited[MAXN], depth[MAXN];
using namespace std;
int walk(int u, int k) {
int v = u;
for (int i = 0; i <= LOGMAXN && v != 0; i++)
if (((1 << i) & k) > 0)
v = table[i][v];
return v;
}
int lca(int u, int v) {
int du, dv;
du = depth[u];
dv = depth[v];
if (du > dv)
u = walk(u, du - dv);
if (dv > du)
v = walk(v, dv - du);
if (u == v)
return u;
for (int i = LOGMAXN; i >= 0; i--) {
if (table[i][u] != table[i][v]) {
u = table[i][u];
v = table[i][v];
}
}
return table[0][u];
}
int distance(int u, int v) {
return depth[u] + depth[v] - 2 * depth[lca(u, v)];
}
int main() {
int n, u, v;
cin >> n;
vector<int> G[n + 2];
for (int i = 1; i < n; i++) {
cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
queue<int> Q;
Q.push(1), depth[1] = 0, visited[1] = 1;
while (!Q.empty()) {
u = Q.front();
Q.pop();
for (auto each: G[u])
if (!visited[each]) {
table[0][each] = u;
depth[each] = depth[u] + 1;
Q.push(each);
visited[each] = 1;
}
}
/* build table */
for (int d = 1; d <= LOGMAXN; d++)
for (int u = 1; u <= n; u++) {
int interv = table[d - 1][u];
table[d][u] = table[d - 1][interv];
}
ll res = 0;
for (int i = 1; i <= n; i++)
for (int j = i + i; j <= n; j += i) {
res = res + distance(i, j) + 1l;
}
cout << res << endl;
}Problem B - POSTTREE
//
// Created by Nivin Anton Alexis lawrence on 2/23/18.
//
#include <iostream>
#include <vector>
#include <bits/stdc++.h>
#define ll long long
#define N (int)(1e5 + 45)
#define LOGN 16
using namespace std;
ll tree[LOGN + 2][N], depth[N], arr[N], n, dp[N], mtree[LOGN + 2][N];
vector<int> G[N];
void dfs(int u, int parent) {
depth[u] = depth[parent] + 1;
int y_ = u;
tree[0][u] = parent;
mtree[0][u] = arr[parent];
for (int i = 1; i <= LOGN; i++) {
tree[i][u] = tree[i - 1][tree[i - 1][u]];
mtree[i][u] = min(mtree[i - 1][u], mtree[i - 1][tree[i - 1][u]]);
}
for (int i = LOGN; i >= 0 && y_ != 0; i--) {
if (mtree[i][y_] >= arr[u]) {
y_ = tree[i][y_];
}
}
y_ = tree[0][y_];
dp[u] = dp[y_] + (depth[u] - depth[y_]) * arr[u];
for (auto aux: G[u])
dfs(aux, u);
}
int main() {
cin >> n;
int aux;
for (int i = 1; i < n; i++) {
cin >> aux;
G[aux].push_back(i + 1);
}
for (int i = 1; i <= n; i++)
cin >> arr[i];
dfs(1, 0);
for (int i = 1; i <= n; i++)
cout << dp[i] << " ";
cout << endl;
} Problem C - A and B and Lecture Rooms
//
// Created by Nivin Anton Alexis lawrence on 2/23/18.
//
#include <iostream>
#include <vector>
#include <queue>
#include <bits/stdc++.h>
#define ll long long
#define N int(1e5 + 45)
#define LOGN 16
using namespace std;
int depth[N], tree[LOGN + 2][N], n, visited[N], nochildren[N];
vector<int> g[N];
int walk(int u, int dist) {
int _y = u;
for (int i = 0; i <= LOGN; i++)
if (((1 << i) & dist) > 0)
_y = tree[i][_y];
return _y;
}
int lca(int u, int v) {
int du, dv;
du = depth[u];
dv = depth[v];
if (du > dv)
u = walk(u, du - dv);
if (dv > du)
v = walk(v, dv - du);
if (u == v)
return u;
for (int i = LOGN; i >= 0; i--) {
if (tree[i][u] != tree[i][v]) {
u = tree[i][u];
v = tree[i][v];
}
}
return tree[0][u];
}
int dfs(int u, int parent) {
tree[0][u] = parent;
depth[u] = depth[parent] + 1;
for (auto v: g[u]) {
if (!visited[v]) {
visited[v] = 1;
nochildren[u] += dfs(v, u);
}
}
nochildren[u] += 1;
return nochildren[u];
}
int dist(int u, int v) {
return depth[u] + depth[v] - 2 * depth[lca(u, v)];
}
int main() {
cin >> n;
int u, v, m;
for (int i = 1; i < n; i++) {
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
cin >> m;
visited[1] = 1;
dfs(1, 0);
for (int i = 1; i <= LOGN; i++)
for (int node = 1; node <= n; node++)
tree[i][node] = tree[i - 1][tree[i - 1][node]];
while (m--) {
cin >> u >> v;
int distance = dist(u, v), res = 0;
if (distance % 2 == 0) {
int lca_uv = lca(u, v), pivot = v, distance_by_2 = distance / 2;
if (depth[lca_uv] + depth[u] > depth[lca_uv] + depth[v])
pivot = u;
int mid_node = walk(pivot, distance / 2);
int u_walk = walk(u, distance_by_2 - 1), v_walk = walk(v, distance_by_2 - 1);
res = n - (nochildren[u_walk] + nochildren[v_walk]);
if (lca_uv != mid_node)
res = nochildren[mid_node] - nochildren[walk(pivot, distance / 2 - 1)];
}
cout << res << endl;
}
}