Pagini recente » Borderou de evaluare (job #779983) | Cod sursa (job #809335) | Cod sursa (job #773753)
Cod sursa(job #773753)
// rezolvare off-line
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
typedef struct { long a,b,nro,rez; } query;
query Q[350005];
long i,n,m,x;
long Nr[350005],nr,act;
vector <long> V[350005];
void DFs ( long varf )
{
Nr[varf]=nr;
nr++;
long i;
for ( i=0; i<V[varf].size(); i++ )
DFs( V[varf][i] );
}
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 )
{
nr++;
Nr[nr]=varf;
long i;
while ( Q[act].b == varf && varf!=0)
{
//printf ("%d %d %d %d\n", act, Q[act].a, Q[act].b, nr );
if ( Q[act].a > nr )
Q[act].rez=0;
else
Q[act].rez=Nr[nr-Q[act].a];
act++;
}
for ( i=0; i<V[varf].size(); i++ )
{
DFs_2( V[varf][i] );
}
nr--;
}
int main()
{
freopen ("stramosi.in","r",stdin);
freopen ("stramosi.out","w",stdout);
scanf ("%d %d", &n, &m);
for ( i=1; i<=n; i++ )
{
scanf ("%d", &x);
V[x].push_back(i);
}
for ( i=1; i<=m; i++ )
{
scanf ("%d %d", &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;
DFs_2(0);
/*for ( i=1; i<=m; i++ )
printf ("%d %d\n", Q[i].a, Q[i].b );*/
sort ( Q+1, Q+m+1, mysort2 );
for ( i=1; i<=m; i++ )
printf ("%d\n",Q[i].rez);
}