Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- using namespace std;
- typedef long long ll;
- const int maxn = 2e5 + 10;
- const int logn = 18;
- int parent[maxn][logn];
- vector<int> depth(maxn, 0);
- vector<int> graph[maxn];
- int timer = 0;
- int in_time[maxn], out_time[maxn];
- void dfs(int node, int prev) {
- timer++;
- in_time[node] = timer;
- parent[node][0] = prev;
- for(int i = 1; i < logn; i++) {
- parent[node][i] = parent[parent[node][i - 1]][i - 1];
- }
- for(int neighbour : graph[node]) {
- if(prev != neighbour) {
- dfs(neighbour, node);
- }
- }
- timer++;
- out_time[node] = timer;
- }
- bool is_ancestor(int a, int b) {
- return (in_time[a] <= in_time[b] and out_time[a] >= out_time[b]);
- }
- int LCA(int a, int b) {
- if(is_ancestor(a, b)) {
- return a;
- }
- if(is_ancestor(b, a)) {
- return b;
- }
- for(int i = logn - 1; i >= 0; i--) {
- if(!is_ancestor(parent[a][i], b)) {
- a = parent[a][i];
- }
- }
- return parent[a][0];
- }
- int main() {
- int n, q;
- cin >> n >> q;
- vector<int> tree(n + 1, -1);
- for(int i = 2; i <= n; i++) {
- cin >> tree[i];
- graph[i].push_back(tree[i]);
- graph[tree[i]].push_back(i);
- parent[i][0] = tree[i];
- }
- parent[1][0] = -1;
- dfs(1, 1);
- while(q--) {
- int a, b;
- cin >> a >> b;
- cout << LCA(a, b) << endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement