forked from Priyansh19077/CP-Templates
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathBinary_Lifting.cpp
67 lines (67 loc) · 1.55 KB
/
Binary_Lifting.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
struct BinaryLifting {
int n;
int maxLog;
ll maxRequirement;
vector<vector<int>> parent;
vector<int> logValues;
bool precomputedLogs = false;
BinaryLifting(int n1, vector<int> *edges, ll requirement, int root) {
n = n1;
parent.resize(n);
maxLog = log2(requirement + 1);
maxRequirement = requirement;
for (int i = 0; i < n; i++) {
parent[i].resize(maxLog + 1);
for (int j = 0; j <= maxLog; j++) {
parent[i][j] = -1;
}
}
fillParentTable(root, edges);
if (maxRequirement <= 1000000LL)
precomputeLogs();
}
void fillParentTable(int root, vector<int> *edges) {
vector<bool> visited(n);
dfsBinaryLifting(root, edges, visited);
int intermediate = -1;
for (int i = 1; i <= maxLog; i++) {
for (int j = 0; j < n; j++) {
intermediate = parent[j][i - 1];
if (intermediate != -1) {
parent[j][i] = parent[intermediate][i - 1];
}
}
}
}
void dfsBinaryLifting(int root, vector<int> *edges, vector<bool> &visited) {
visited[root] = true;
for (auto i : edges[root]) {
if (!visited[i]) {
parent[i][0] = root;
dfsBinaryLifting(i, edges, visited);
}
}
}
void precomputeLogs() {
precomputedLogs = true;
logValues.resize(maxRequirement + 1);
logValues[1] = 0;
for (int i = 2; i <= maxRequirement; i++) {
logValues[i] = logValues[i / 2] + 1;
}
}
int kthParent(int start, int k) {
int a = start;
while (k > 0) {
int x = getLog(k);
a = parent[a][x];
if (a == -1)
return a;
k -= (1 << x);
}
return a;
}
int getLog(ll x) {
return precomputedLogs ? logValues[x] : log2(x);
}
};