Cod sursa(job #2686039)

Utilizator ionutpop118Pop Ioan Cristian ionutpop118 Data 18 decembrie 2020 13:59:54
Problema Lowest Common Ancestor Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.02 kb
#include <cstdio>
#include <vector>
#include <cmath>
using namespace std;

/// Depth-first search of the graph
void build_father(int node, int current_level, vector <bool> &viz, vector < vector <int> > &graph, vector < vector <int> > &father, vector <int> &level) {
	viz[node] = 1;
    level[node] = current_level;
	for (unsigned int i = 0; i < graph[node].size(); ++i) {
		if (viz[graph[node][i]] == 0) {
            father[0][graph[node][i]] = node;
			build_father(graph[node][i], current_level + 1, viz, graph, father, level);
		}
	}
}

/// Gets the fathers list from a graph
void get_father(int root, int &n, vector < vector <int> > &graph, vector < vector <int> > &father, vector <int> &level) {
	vector <bool> viz(n + 1, 0);
	build_father(root, 0, viz, graph, father, level);
}

/// Gets the k-th father of a node
int get_kth_father(int node, int k, vector < vector <int> > &father) {
    for (int i = 0; (1 << i) <= k; ++i) {
        if ((k & (1 << i)) != 0) {
            node = father[i][node];
        }
    }
    return node;
}

/// Calculates for each node his 1<<k-th father
void generate_father(int &n, int &lg, vector < vector <int> > &father) {
    for (int i = 1; i <= lg; ++i) {
        for (int j = 1; j <= n; ++j) {
            father[i][j] = father[i - 1][father[i - 1][j]];
        }
    }
}
/// Gets the LCA of 2 nodes
int get_lca(int x, int y, int &lg, vector <int> & level, vector < vector <int> > &father) {
    if (level[x] > level[y]) {
        swap(x, y);
    }

    y = get_kth_father(y, level[y] - level[x], father);
    if (x == y) {
        return x;
    }

    for (int j = lg - 1; j >= 0; --j) {
        if (father[j][x] != father[j][y]) {
            x = father[j][x];
            y = father[j][y];
        }
    }
    return father[0][x];
}

vector <int> lca(vector< vector<int> > &graph, vector< pair <int, int> > &queries) {
    int n = graph.size() + 1;
    int q = queries.size();
    int lg = (int)log2(n) + 1;

    vector < vector <int> > father(lg + 1, vector <int> (n + 1, 0));
    vector <int> level(n + 1); // Level of a node in the Euler tour

    get_father(1, n, graph, father, level);
    generate_father(n, lg, father);

    vector <int> answer; // Query answers
    for (int i = 0; i < q; ++i) {
        answer.push_back(get_lca(queries[i].first, queries[i].second, lg, level, father));
    }
    return answer;
}

int main() {
	freopen("lca.in", "r", stdin);
	freopen("lca.out", "w", stdout);

	int n, m, x, y;
	scanf("%d %d", &n, &m);
	vector< vector<int> > g(n + 1);
	vector< pair <int, int> > q;

    for (int i = 2; i <= n; ++i) {
		scanf("%d", &x);
		g[i].push_back(x);
		g[x].push_back(i);
	}

	/*for (int i = 2; i <= n; ++i) {
        scanf("%d", &x);
        g[x].push_back(i);
        g[i].push_back(x);
	}*/

	for (int i = 1; i <= m; ++i) {
		scanf("%d %d", &x, &y);
		q.push_back(make_pair(x, y));
	}

	vector <int> ans = lca(g, q);

    for (int i = 0; i < m; ++i) {
		printf("%d\n", ans[i]);
	}

	return 0;
}