Cod sursa(job #2565464)

Utilizator MihneaGhiraMihnea MihneaGhira Data 2 martie 2020 14:17:09
Problema Lowest Common Ancestor Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include<fstream>
#include<vector>
using namespace std;
ifstream fin("lca.in");
ofstream fout("lca.out");
int n,m,X,Y;
int nivel[100010],f[100010],T[100010];
vector <int> L[100010];

void dfs(int nod, int niv){
    nivel[nod]=niv;
    f[nod]=1;
    for(int i=0;i<L[nod].size();i++)
        if(f[L[nod][i]]==0)
            dfs(L[nod][i],niv+1);
}

int main(){
    fin>>n>>m;
    for(int i=1;i<n;i++){
        fin>>T[i+1];
        L[T[i+1]].push_back(i+1);
    }
    dfs(1,0);
    for(int i=1;i<=m;i++){
        fin>>X>>Y;
        while(nivel[X]>nivel[Y]){
            X=T[X];
        }
        while(nivel[Y]>nivel[X]){
            Y=T[Y];
        }
        if(X==Y)
            fout<<X<<"\n";
        else{
            while(T[X]!=T[Y]){
                X=T[X];
                Y=T[Y];
            }
            fout<<T[X]<<"\n";
        }
    }
    return 0;
}