CP-codes/Tree/lca_binarylifting.cpp at master · hemant2132/CP-codes · GitHub

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
68
69
70
71
72
73
74
75
vector<int> lev(N), par(N);
int anc[N][20];

void dfsInit(int x, int p) {
    if (p != -1)
        lev[x] = lev[p] + 1;

    par[x] = p;

    for (auto c : adj[x]) {
        if (c != p) {
            dfsInit(c, x);
        }
    }
}

void computeAncestors(int n) {
    for (int i = 1; i <= n; ++i)
        anc[i][0] = par[i];

    for (int j = 1; (1 << j) <= n; ++j) {
        for (int i = 1; i <= n; ++i) {
            if (anc[i][j - 1] != -1)
                anc[i][j] = anc[anc[i][j - 1]][j - 1];
        }
    }
}

int lca(int a, int b) {
    if (lev[a] < lev[b])
        swap(a, b);

    int lg;
    for (lg = 1; (1 << lg) <= lev[a]; ++lg) {}
    --lg;

    for (int i = lg; i >= 0; --i) {
        if (lev[a] - (1 << i) >= lev[b])
            a = anc[a][i];
    }

    if (a == b) return a;

    for (int i = lg; i >= 0; --i) {
        if (anc[a][i] != -1 && anc[a][i] != anc[b][i])
            a = anc[a][i], b = anc[b][i];
    }

    return anc[a][0];
}

int getKthAncestor(int x, int k) { // returns kth ancestor of 'x'
    for (int i = 0; k; ++i, k /= 2) {
        if (k % 2)
            x = anc[x][i];
    }

    return x;
}

int getPathValue(int a, int b) { // returns value on the path "a to b" where b is an ancestor of a
    int lg;
    for (lg = 1; (1 << lg) <= lev[a]; ++lg) {}
    --lg;

    int res = 0;
    for (int i = lg; i >= 0; --i) {
        if (lev[a] - (1 << i) >= lev[b]) {
            // res = max(res, mx[a][i]);
            a = anc[a][i];
        }
    }

    return res;
}