Pagini recente » Cod sursa (job #2523300) | Cod sursa (job #1050197) | Cod sursa (job #2824523) | Cod sursa (job #1481532) | Cod sursa (job #2179204)
#include <fstream>
#include <vector>
#define NMAX 100005
using namespace std;
ifstream f("lca.in");
ofstream g("lca.out");
int i,n,t,doi[2*NMAX],x,y,p[NMAX],d,nr,m;
vector <int> G[NMAX];
struct du{
int n,m;}rmq[2*NMAX][20];
void dfs(int nod,int nivel){
rmq[++nr][0].m=nivel;
rmq[nr][0].n=nod;
if(!p[nod])
p[nod]=nr;
for(int i=0;i<G[nod].size();i++){
dfs(G[nod][i],nivel+1);
rmq[++nr][0].n=nod;
rmq[nr][0].m=nivel;
}
}
void pre(){
for(i=1;i<=nr;i++){
t=i;
while(t>=2){
doi[i]++;
t/=2;
}
}
}
void RMQ(){
for(int j=1;j<=doi[nr];j++){
int a=1;
for(i=1;i+(1<<j)-1<=nr;i++)
if(rmq[i][j-1].m>rmq[i+(1<<(j-1))][j-1].m){
rmq[i][j]=rmq[i+(1<<(j-1))][j-1];
}
else
rmq[i][j]=rmq[i][j-1];
}
}
int main()
{
f>>n>>m;
for(i=2;i<=n;i++){
f>>x;
G[x].push_back(i);
}
dfs(1,1);
pre();
RMQ();
for(i=1;i<=m;i++){
f>>x>>y;
if(p[x]>p[y])
swap(x,y);
d=doi[p[y]-p[x]+1];
if(rmq[p[x]][d].m<rmq[p[y]-(1<<d)+1][d].m)
g<<rmq[p[x]][d].n<<'\n';
else
g<<rmq[p[y]-(1<<d)+1][d].n<<'\n';
}
return 0;
}