Cod sursa(job #2680043)

Utilizator ionutpop118Pop Ioan Cristian ionutpop118 Data 2 decembrie 2020 13:41:36
Problema Lowest Common Ancestor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.51 kb
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

const int NMAX = 100000; // Maximum number of nodes
const int LGMAX = 18; // Base 2 logarithm of NMAX

vector <int> children[NMAX + 5]; // List of children for each node
int euler[2 * NMAX + 1]; // Euler tour of a tree
int first[NMAX + 1]; // First appearance
int tour_length; // Length of the Euler tour
int level[2 * NMAX + 5]; // Level of a node in the Euler tour

int rmq[LGMAX + 1][2 * (NMAX + 1)]; // RMQ
int lg[2 * (NMAX + 1)]; // Vector of logarithms

void dfs(int node, int current_level) {
    euler[++tour_length] = node;
    level[tour_length] = current_level;
    first[node] = tour_length;

    for (int i = 0; i < children[node].size(); ++i)
    {
        dfs(children[node][i], current_level + 1);
        euler[++tour_length] = node;
        level[tour_length] = current_level;
    }
}

void generate_euler_tour() { // Generates the Euler tour
    dfs(1, 0); // node 1 is root in this scenario
}

void build_rmq() { // Generates the RMQ
    // Calculates log in base 2 of i
    for (int i = 2; i <= tour_length; ++i) {
        lg[i] = 1 + lg[(i >> 1)];
    }

    // Builds RMQ
    for (int i = 1; i <= tour_length; ++i) {
        rmq[0][i] = i;
    }

    for (int i = 1; i <= lg[tour_length]; ++i) {
        for (int j = 1; j <= tour_length; ++j) {
            if ((1 << i) <= j) {
                rmq[i][j] = rmq[i - 1][j];
                if (level[rmq[i][j]] > level[rmq[i - 1][j - (1 << (i - 1))]]) {
                    rmq[i][j] = rmq[i - 1][j - (1 << (i - 1))];
                }
            }
        }
    }
}

int get_LCA(int x, int y) { // Returns the LCA of 2 nodes
    x = first[x], y = first[y];
    if (x > y)
        swap(x, y);
    int mid = lg[y - x + 1];
    int ans = rmq[mid][y];
    if (level[ans] > level[rmq[mid][x + (1 << mid) - 1]]) {
        ans = rmq[mid][x + (1 << mid) - 1];
    }
    return euler[ans];
}

int main() {
    freopen("lca.in", "r", stdin);
    freopen("lca.out", "w", stdout);
    int n; // Tree size
    int m; // Number of queries

    // Input
    scanf("%d%d", &n, &m);
    for (int i = 2; i <= n; ++i) {
        int x; // Father of node i
        scanf("%d", &x);
        children[x].push_back(i);
    }

    generate_euler_tour();
    build_rmq();

    // Queries
    for (int i = 1; i <= m; ++i) {
        int x, y; // Two nodes
        scanf("%d%d", &x, &y);
        printf("%d\n", get_LCA(x, y));
    }

    return 0;
}