Cod sursa(job #2408401)

Utilizator FunnyStockyMihnea Andreescu FunnyStocky Data 17 aprilie 2019 21:59:35
Problema Lowest Common Ancestor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.98 kb
/**
 *
 * LCA
 *
**/
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

const int N=100000+7;
const int LG=19;

int n,t;
vector <int> g[N];
int dep[N];
int euler[3*N],top;
int first[N],last[N];

struct kek
{
        int fi;
        int se;
};

kek rmq[3*N][LG];
int mylog[3*N];

void __read()
{
        cin>>n>>t;
        for(int i=2;i<=n;i++)
        {
                int dad;
                cin>>dad;
                g[dad].push_back(i);
        }
}

void build(int nod)
{
        euler[++top]=nod;
        first[nod]=last[nod]=top;
        for(auto &nou:g[nod])
        {
                dep[nou]=1+dep[nod];
                build(nou);
                euler[++top]=nod;
                last[nod]=top;
        }
}

/**kek Min(kek a,kek b)
{
        if(a.fi<b.fi)
        {
                return a;
        }
        else
        {
                return b;
        }
}

void buildRMQ()
{
        for(int i=2;i<=top;i++)
        {
                mylog[i]=1+mylog[i/2];
        }
        for(int i=1;i<=top;i++)
        {
                rmq[i][0]={dep[euler[i]],i};
        }
        for(int k=1;(1<<k)<=top;k++)
        {
                for(int i=1;i+(1<<k)-1<=top;i++)
                {
                        rmq[i][k]=Min(rmq[i][k-1],rmq[i+(1<<(k-1))][k-1]);
                }
        }
}

int lca(int a,int b)
{
        if(first[a]>first[b])
        {
                swap(a,b);
        }
        int st=last[a];
        int dr=first[b];
        int k=mylog[dr-st+1];
        kek sol=Min(rmq[st][k],rmq[dr-(1<<k)+1][k]);
        return euler[sol.se];
}**/

int main()
{
        freopen("lca.in","r",stdin);
        freopen("lca.out","w",stdout);
        __read();
        build(1);
       /** buildRMQ();
        while(t--)
        {
                int a,b;
                cin>>a>>b;
                cout<<lca(a,b)<<"\n";
        }**/
        return 0;
}