Test/yosupo-judge/LowestCommonAncestor.test.cpp

View this file on GitHub
Last update: 2021-06-18 21:14:35+09:00
Problem: https://judge.yosupo.jp/problem/lca

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/lca"

#include<bits/stdc++.h>
using namespace std;

#include"../../Other/Template.cpp"
#include"../../Graph/LowestCommonAncestor.cpp"

int main() {
    cin >> N;
    int Q;
    cin >> Q;
    for(int i = 0;i < N - 1;i++) {
        int p;
        cin >> p;
        graph[i + 1].push_back(p);
        graph[p].push_back(i + 1);
    }
    init(N);
    for(int i = 0;i < Q;i++) {
        int u,v;
        cin >> u >> v;
        cout << LCA(u,v) << endl;
    }
}

#line 1 "Test/yosupo-judge/LowestCommonAncestor.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/lca"

#include<bits/stdc++.h>
using namespace std;

#line 1 "Other/Template.cpp"
constexpr int Inf = 2000000030;
constexpr long long INF= 2000000000000000000;

template<typename T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }
template<typename T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }
#line 1 "Graph/LowestCommonAncestor.cpp"
int N;
vector<int> graph[500010];

int root = 0;

int parent[50][500010];
int depth[500010];

void dfs(int v,int p,int d) {
    parent[0][v] = p;
    depth[v] = d;
    for(int i = 0;i < graph[v].size();i++) {
        if(graph[v][i] != p) {
            dfs(graph[v][i],v,d + 1);
        }
    }
}

void init(int V) {
    dfs(root,-1,0);
    for(int k = 0;k + 1 < 50;k++) {
        for(int v = 0;v < V;v++) {
            if(parent[k][v] < 0) {
                parent[k + 1][v] = -1;
            }
            else {
                parent[k + 1][v] = parent[k][parent[k][v]];
            }
        }
    }
}

int LCA(int u,int v) {
    if(depth[u] > depth[v]) {
        swap(u,v);
    }
    for(int k = 0;k < 50;k++) {
        if((depth[v] - depth[u]) >> k & 1) {
            v = parent[k][v];
        }
    }
    if(u == v) return u;
    for(int k = 49;k >= 0;k--) {
        if(parent[k][u] != parent[k][v]) {
            u = parent[k][u];
            v = parent[k][v];
        }
    }
    return parent[0][u];
}
#line 8 "Test/yosupo-judge/LowestCommonAncestor.test.cpp"

int main() {
    cin >> N;
    int Q;
    cin >> Q;
    for(int i = 0;i < N - 1;i++) {
        int p;
        cin >> p;
        graph[i + 1].push_back(p);
        graph[p].push_back(i + 1);
    }
    init(N);
    for(int i = 0;i < Q;i++) {
        int u,v;
        cin >> u >> v;
        cout << LCA(u,v) << endl;
    }
}