Cod sursa(job #1679040)

Utilizator robertkarolRobert Szarvas robertkarol Data 7 aprilie 2016 17:28:42
Problema Lowest Common Ancestor Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("lca.in");
ofstream fout("lca.out");
int n,m,i,t[100001],t2[100001],H,niv[100001],x,y;
bool frunza[100001];
void inaltime(int nod)
{
    int h=0;
    while(nod)
    {
        h++;
        nod=t[nod];
    }
    H=max(H,h);
}
void df(int nod, int tata, int nivel)
{
    int i;
    t2[nod]=tata; niv[nod]=nivel;
    if(nivel%H==0) tata=nod;
    for(i=1;i<=n;i++)
        if(t[i]==nod) df(i,tata,nivel+1);
}
int lca(int x, int y)
{
    while(t2[x]!=t2[y])
        if(niv[x]>niv[y]) x=t2[x];
        else y=t2[y];
    while(x!=y)
        if(niv[x]>niv[y]) x=t[x];
        else y=t[y];
   return x;
}
int main()
{
    fin>>n>>m;
    for(i=2;i<=n;i++)
    {
        fin>>t[i];
        frunza[t[i]]=1; /// 0 <=> frunza
    }
    for(i=1;i<=n;i++)
        if(!frunza[i])
            inaltime(i);
    df(1,0,1);
    for(i=1;i<=m;i++)
    {
        fin>>x>>y;
        fout<<lca(x,y)<<"\n";
    }
    return 0;
}