Pagini recente » Cod sursa (job #2597831) | Cod sursa (job #2900741) | Cod sursa (job #970146) | Monitorul de evaluare | Cod sursa (job #2355876)
#include <bits/stdc++.h>
using namespace std;
ifstream fi("lca.in");
ofstream fo("lca.out");
const int NMAX = 1e5 + 5;
const int LOG = 25;
struct multe
{
int val, poz;
};
vector <int> G[NMAX];
int p[NMAX], niv[NMAX];
int n;
vector <int> repr;
multe rmq[LOG][2 * NMAX];
void dfs(int nod)
{
repr.push_back(nod);
for (auto v: G[nod])
{
niv[v] = niv[nod] + 1;
dfs(v);
}
}
void getRmq()
{
int m = repr.size();
for (int j = 0; j < m; j++)
rmq[0][j] = {niv[repr[j]], repr[j]};
for (int i = 1; (1 << i) <= m; i++)
{
for (int j = 0; j < m; j++)
if (j + (1 << i) - 1 < m) /// intra
{
if (rmq[i - 1][j].val > rmq[i - 1][j + (1 << (i - 1))])
rmq[i][j] = rmq[i - 1][j];
else
rmq[i][j] = rmq[i - 1][j + (1 << (i - 1))];
}
}
}
int main()
{
fi >> n;
for (int i = 2; i <= n; i++)
{
fi >> p[i];
G[p[i]].push_back(i);
}
dfs(1);
getRmq();
return 0;
}