Cod sursa(job #1655127)

Utilizator AlexandraaaaMereu Alexandra Alexandraaaa Data 17 martie 2016 19:13:36
Problema Lowest Common Ancestor Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 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 vezi(int x, int y){
	if (H[x] != H[y]){
		int max, min;
		if (H[x] > H[y]){
			max = x;
			min = y;
		}
		else{
			max = y;
			min = x;
		}
		while (H[max] > H[min])
			max = S[0][max];
		x = max;
		y = min;
	}

	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]){
		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;
}