Cod sursa(job #1892412)

Utilizator megabytes112Bigfoot din padure megabytes112 Data 24 februarie 2017 22:34:15
Problema Lowest Common Ancestor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream f("lca.in");
ofstream g("lca.out");

const int h= 200;
int n, m, i, tt[100005], tataie[100005], x, y;
int Niv[100005];
bool viz[100005];
vector <int> ls[100005];

void df(int nod, int rad, int niv) {
    int i;
    viz[nod] = 1;
    tataie[nod] = rad;
    Niv[nod] = niv;
    if (niv%h == 0)
        rad = nod;
    for (i = 0; i < ls[nod].size(); i++)
        if (viz[ls[nod][i]] == 0)
            df(ls[nod][i], rad, niv+1);
}

int query(int x, int y) {
    while (tataie[x] != tataie[y]) {
        if (Niv[x] > Niv[y])
            x = tataie[x];
        else y = tataie[y];
    }
    while (x != y) {
        if (Niv[x] > Niv[y])
            x = tt[x];
        else y = tt[y];
    }
    return x;
}

int main() {
    f >> n >> m;
    for (i = 2; i <= n; i++) {
        f >> tt[i];
        ls[tt[i]].push_back(i);
    }
    df(1,1,0);
    while (m--) {
        f >> x >> y;
        g << query(x,y) << '\n';
    }
    return 0;
}