跑路

第一行两个正整数 n, m
第二行 n-1 个正整数，其中第 i 个数 $f_i$ 表示点 i+1 与 $f_i$ 之间有一条边
（保证 $1\leq f_i\leq i$ ）
第三行一个正整数 l
第四行 m 个非负整数，为每次询问的参数 d

C++11(clang++ 3.9) 解法, 执行用时: 1368ms, 内存消耗: 140784K, 提交时间: 2019-06-28 21:35:48

#include <cstdio>
#include <vector>

using std::vector;

const int MAXN=3000011;

inline void relax(int &p, int v){
	if(p<v)	p=v;
}

int N, M, L;
int F[MAXN];
int Dep[MAXN], Md[MAXN];
int Ms[MAXN];
int Ans[MAXN];
vector<int> Add[MAXN];

int Val[MAXN];

int main(){
	
	scanf("%d%d", &N, &M);
	
	for(int i=2;i<=N;++i)	scanf("%d", &F[i]);
	
	scanf("%d", &L);
	
	Dep[1]=1;
	for(int i=2;i<=N;++i)	Dep[i]=Dep[F[i]]+1;
	
	for(int i=1;i<=N;++i)	Md[i]=Dep[i];
	for(int i=N;i>=2;--i)
		relax(Md[F[i]], Md[i]);
	
	for(int i=N, f;i>=2;--i){
		f=F[i];
		if(Md[Ms[f]]<Md[i])	Ms[f]=i;
	}
	
	for(int i=N, f;i>=2;--i){
		f=F[i];
		if(Ms[f]==i)	continue;
		for(int k=Dep[f]+1;k<=Md[i];++k)
			Add[k].push_back(k-Dep[f]);
	}
	
	for(int i=1;i<=Md[1];++i)	Add[i].push_back(i);
	
	for(int i=1;i<=Md[1];++i){
		Ans[i]=Ans[i-1];
		for(int p=0, s=Add[i].size(), k;p<s;++p){
			k=Add[i][p];
			++Val[k];
			if(Val[k]<=L)	++Ans[i];
		}
	}
	
	for(int v;M--;){
		scanf("%d", &v);
		++v;if(v>Md[1])	v=Md[1];
		printf("%d\n", Ans[v]);
	}
	
	return 0;
}

/*
6 3
1 1 3 3 3
2
0
1
2

1
3
4

*/

详情