Cod sursa(job #1655149)

Utilizator AlexandraaaaMereu Alexandra Alexandraaaa Data 17 martie 2016 19:28:53
Problema Lowest Common Ancestor Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <string>
#define maxN 100000 + 5

using namespace std;

int S[30][maxN], H[maxN], viz[maxN];
vector<int> TR[maxN];
int n;

int log(int n){
	int a = 0, b = 1;
	while ((b << 1) <= n){
		a++;
		b <<= 1;
	}
	return a;
}

int t(int q, int p){
	int i = 0;
	while (p){
		if (p % 2)
			q = S[i][q];
		i++;
		p >>= 1;
	}
	return q;
}

int vezi(int x, int y){
	if (H[x] != H[y]){
		if (H[x] > H[y])
			x = t(x, H[x] - H[y]);
		else
			y = t(y, H[y] - H[x]);
	}

	if (x == y)
		return x;

	int t = log(n);
	while (t >= 0){
		if (S[t][x] != S[t][y]){
			x = S[t][x];
			y = S[t][y];
		}
		t--;
	}
	return S[0][x];
}

void h(int i, int lv){
	H[i] = lv;
	if (!viz[i]){
		viz[i] = 1;
		for (int k = 0; k < TR[i].size(); ++k)
			h(TR[i][k], lv + 1);
	}
}

int main()
{
	ifstream f("lca.in");
	ofstream g("lca.out");

	int m;

	f >> n >> m;
	for (int i = 2; i <= n; ++i){
		f >> S[0][i];
		TR[S[0][i]].push_back(i);
	}

	h(1, 0);

	int lim = log(n);
	for (int i = 1; i <= lim; ++i)
		for (int j = 1; j <= n; ++j)
			S[i][j] = S[i-1][S[i-1][j]];

	for (int k = 0; k < m; ++k){
		int x, y;
		f >> x >> y;
		g << vezi(x, y) << "\n";
	}

	f.close();
	g.close();

	return 0;
}