题意
给定一棵树,每次询问给出一个点
解析
考虑用一个时间戳,记录每一个点的入栈时间
时间复杂度
代码
#include<bits/stdc++.h> using namespace std; const int N=2e5+5; struct node{ int to,nxt; }e[N<<1]; int cnt,head[N]; inline void add(int u,int v){ e[++cnt].to=v; e[cnt].nxt=head[u]; head[u]=cnt; } int n,in[N],out[N],Cnt,dep[N]; vector<int> v[N];//不要不会用 vector 啊!!! inline void dfs(int u){ in[u]=++Cnt; v[dep[u]].push_back(in[u]); for(int i=head[u];i;i=e[i].nxt){ int v=e[i].to; dep[v]=dep[u]+1; dfs(v); } out[u]=++Cnt; } int T; int main(){ scanf("%d",&n); for(int i=2,x;i<=n;i++){ scanf("%d",&x); add(x,i); } dfs(1); scanf("%d",&T); while(T--){ int u,d; scanf("%d%d",&u,&d); printf("%lld\n",lower_bound(v[d].begin(),v[d].end(),out[u])-lower_bound(v[d].begin(),v[d].end(),in[u])); } return 0; }