Cod sursa(job #2084697)

Utilizator TherevengerkingSurani Adrian Therevengerking Data 9 decembrie 2017 11:32:02
Problema Lowest Common Ancestor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("lca.in");
ofstream fout("lca.out");
#define pb push_back
const int Nmax = 100000 + 5;
int n, m, f[Nmax], bf[Nmax], lgn, g[Nmax], lm;
vector<int>v[Nmax];
int lca(int a, int b)
{
    if(g[a] < g[b])swap(g[a], g[b]);
    while(g[a] > g[b])
    {
        if(g[a] - lgn >= g[b])
            a = bf[a];
        else a = f[a];
    }
    while(a != b)
    {
        a = f[a];
        b = f[b];
    }
    return a;
}
void dfs(int nod)
{
    for(auto i : v[nod])
        if(i != f[nod])
        {
            g[i] = g[nod] + 1;
            if(g[i] > lgn)lgn = g[i];
            dfs(i);
        }
}
void dfs1(int nod, int bgf, int lm)
{
    if(lm % lgn == 1)bgf = nod;
    for(auto i : v[nod])
        if(i != f[nod])
        {
            bf[i] = bgf;
            dfs1(i, bgf, lm + 1);
        }
}
int main()
{
    fin >> n >> m;
    f[1] = 1; g[1] = 1;
    for(int i = 1, a; i < n; ++i)
    {
        fin >> a;
        f[i + 1] = a;
        v[a].pb(i + 1);
    }
    dfs(1);
    lgn = sqrt(lgn);
    lm = 0;
    dfs1(1, 1, 1);
    for(int i = 1, a, b; i <= m; ++i)
    {
        fin >> a >> b;
        fout << lca(a, b) << '\n';
    }
    return 0;
}