<commit_before>///////////////////////////////////////////////////////////////////////
//  Lowest Common Ancestor (LCA)
//  O(lgn) per query
//  Link: http://www.spoj.com/status/LCA/
///////////////////////////////////////////////////////////////////////

#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>

using namespace std;

#define SZ(x) ((int)((x).size()))

class LCA {
public:
    typedef vector<int> VI;
    typedef vector<VI> VVI;
    typedef vector<VVI> VVVI;
    VI depths;
    VVI parents;
    VVVI V;
    int N, root, max_lvl;
    // Vertices are 0-based indexed.
    LCA (int root_, VVI graph) {
        root = root_; N = graph.size(); depths.resize(N);
        max_lvl = 1; while ((1<<max_lvl) < N) max_lvl++;
        V.resize(max_lvl, vector<vector<int>>(N));
        parents.resize(max_lvl, VI(N));
        build_lca(root, -1, graph, 0);
        for (int i = 1; i < max_lvl; i++)
            for (int j = 0; j < N; j++)
                if (parents[i - 1][j] != -1) {
                    parents[i][j] = parents[i - 1][parents[i - 1][j]];
                }
    }
    vector<int> res;
    int lca(int u, int v) {
        if (depths[u] < depths[v]) swap(u, v);
        int diff_dep = depths[u] - depths[v];
        for (int i = 0; i < max_lvl; i++)
            if ((1<<i) & diff_dep) {
                u = parents[i][u];
            }
        if (u == v) {
            return u;
        }
        for (int i = max_lvl - 1; i >= 0; i--) {
            if (parents[i][u] != parents[i][v]) {
                u = parents[i][u];
                v = parents[i][v];
            }
        }
        return parents[0][u];
    }
    int get_depth(int u) { return depths[u]; }
private:
    void build_lca(int at, int par, VVI &adj, int dep) {
        parents[0][at] = par;
        depths[at] = dep;
        for (auto v : adj[at]) {
            if (v != par) {
                build_lca(v, at, adj, dep + 1);
            }
        }<commit_msg>Update LCA.cpp<commit_after>///////////////////////////////////////////////////////////////////////
//  Lowest Common Ancestor (LCA)
//  O(lgn) per query
//  Link: http://www.spoj.com/status/LCA/
///////////////////////////////////////////////////////////////////////

#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>

using namespace std;

#define SZ(x) ((int)((x).size()))

class LCA {
public:
    typedef vector<int> VI;
    typedef vector<VI> VVI;
    typedef vector<VVI> VVVI;
    VI depths;
    VVI parents;
    VVVI V;
    int N, root, max_lvl;
    // Vertices are 0-based indexed.
    LCA (int root_, VVI graph) {
        root = root_; N = graph.size(); depths.resize(N);
        max_lvl = 1; while ((1<<max_lvl) < N) max_lvl++;
        V.resize(max_lvl, vector<vector<int>>(N));
        parents.resize(max_lvl, VI(N));
        build_lca(root, -1, graph, 0);
        for (int i = 1; i < max_lvl; i++)
            for (int j = 0; j < N; j++)
                if (parents[i - 1][j] != -1) {
                    parents[i][j] = parents[i - 1][parents[i - 1][j]];
                }
    }
    int lca(int u, int v) {
        if (depths[u] < depths[v]) swap(u, v);
        int diff_dep = depths[u] - depths[v];
        for (int i = 0; i < max_lvl; i++)
            if ((1<<i) & diff_dep) {
                u = parents[i][u];
            }
        if (u == v) {
            return u;
        }
        for (int i = max_lvl - 1; i >= 0; i--) {
            if (parents[i][u] != parents[i][v]) {
                u = parents[i][u];
                v = parents[i][v];
            }
        }
        return parents[0][u];
    }
    int get_depth(int u) { return depths[u]; }
private:
    void build_lca(int at, int par, VVI &adj, int dep) {
        parents[0][at] = par;
        depths[at] = dep;
        for (auto v : adj[at]) {
            if (v != par) {
                build_lca(v, at, adj, dep + 1);
            }
        }
{'fraction_non_alphanumeric': 0.23049464558898522, 'fraction_numerical': 0.009178990311065782, 'mean_word_length': 1.3646775165762508, 'pattern_counts': {'":': 0, '<': 40, '<?xml version=': 0, '>': 24, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6235188', 'n_tokens_mistral': 1395, 'n_tokens_neox': 1341, 'n_words': 353}