Cod sursa(job #773788)
// rezolvare off-line
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
typedef struct { long a,b,nro,rez; } query;
query Q[300005];
long i,n,m,x;
long Nr[300005],nr,act;
long Nr2[300005],nr2;
long C[300005];
vector <long> V[300005];
void DFs ( long varf )
{
nr2=1;
while ( nr2>0 )
{
//printf ("%d %d\n",varf,nr);
if ( !C[varf] )
{
Nr[varf]=nr;
nr++;
}
if ( C[varf] == (V[varf].size() ))
// trecem inapoi
{
nr2--;
varf=Nr2[nr2];
}
else{
// mai bagam pe cineva in parcurgere
nr2++;
Nr2[nr2]=V[varf][C[varf]];
C[varf]++;
varf=Nr2[nr2];
}
}
}
bool mysort ( query a, query b )
{
return Nr[a.b]<Nr[b.b];
}
bool mysort2 ( query a, query b )
{
return a.nro<b.nro;
}
void DFs_2 ( long varf )
{
nr2=1;
while ( nr2>0 )
{
if ( !C[varf] )
{
while ( Q[act].b == varf && varf!=0)
{
if ( Q[act].a > nr2 )
Q[act].rez=0;
else
Q[act].rez=Nr2[nr2-Q[act].a];
act++;
}
}
if ( C[varf] == (V[varf].size() ))
// trecem inapoi
{
nr2--;
varf=Nr2[nr2];
}
else{
// mai bagam pe cineva in parcurgere
nr2++;
Nr2[nr2]=V[varf][C[varf]];
C[varf]++;
varf=Nr2[nr2];
}
}
}
int main()
{
freopen ("stramosi.in","r",stdin);
freopen ("stramosi.out","w",stdout);
cin>>n>>m;
for ( i=1; i<=n; i++ )
{
cin>>x;
V[x].push_back(i);
}
for ( i=1; i<=m; i++ )
{
cin>>Q[i].b>>Q[i].a;
Q[i].nro=i;
}
DFs(0);
sort ( Q+1, Q+m+1, mysort );
nr=0;
act=1;
Nr[0]=0;
for ( i=0; i<=n; i++ )
C[i]=0;
DFs_2(0);
sort ( Q+1, Q+m+1, mysort2 );
for ( i=1; i<=m; i++ )
printf ("%d\n",Q[i].rez);
}