RT

TLE on 8 9 10 11

花了两份提交记录（1 2）交 exit(1) 夹了一下发现好像是树剖 la 假了

都是根据理解瞎实现的可能并不是很优美

#include <bits/stdc++.h>

const int Maxn = 1e6 + 5;

int n, m, x, y, dep[Maxn], siz[Maxn], h[Maxn], top[Maxn], fa[Maxn], cnt[Maxn], dfn[Maxn], dcnt, dir[Maxn], ver[Maxn << 1], nxt[Maxn << 1], hd[Maxn], ecnt;
void add(int u, int v) {ecnt++; ver[ecnt] = v; nxt[ecnt] = hd[u]; hd[u] = ecnt;}
void dfs(int u, int f) {
	dep[u] = dep[fa[u] = f] + (siz[u] = 1);
	for(int i = hd[u]; i; i = nxt[i]) {
		int v = ver[i]; if(v == f) continue;
		dfs(v, u); siz[u] += siz[v];
		if(siz[v] > siz[h[u]]) h[u] = v;
	}
}
void dfs1(int u) {
	if(!top[u]) top[u] = u; if(h[u]) top[h[u]] = top[u];
	dir[dfn[u] = ++dcnt] = u;
	if(h[u]) dfs1(h[u]);
	for(int i = hd[u]; i; i = nxt[i]) {
		int v = ver[i]; if(v == fa[u] || v == h[u]) continue;
		dfs1(v);
	}
}
int la(int u, int k) {
	while(dep[u] - dep[top[u]] < k && u != 1) {
		k -= dep[u] - dep[top[u]] + 1;
		u = fa[top[u]];
	}
	return dir[dfn[u] - k];
}

std::vector<std::pair<int, int> > qs[Maxn]; int ans[Maxn]; 

void dfs2(int u) {
	cnt[dep[u]]--; for(int i = hd[u]; i; i = nxt[i]) if(ver[i] != fa[u]) dfs2(ver[i]);
}
void dfs3(int u) {
	cnt[dep[u]]++; for(int i = hd[u]; i; i = nxt[i]) if(ver[i] != fa[u]) dfs3(ver[i]);
} 
void dfs4(int u) {
	for(int i = hd[u]; i; i = nxt[i]) {
		if(ver[i] == fa[u] || ver[i] == h[u]) continue;
		dfs4(ver[i]); dfs2(ver[i]);
	}
	if(h[u]) dfs4(h[u]);
	for(int i = hd[u]; i; i = nxt[i]) {
		if(ver[i] == fa[u] || ver[i] == h[u]) continue;
		dfs3(ver[i]);
	}
	++cnt[dep[u]];
	for(auto p : qs[u]) {
		int qid = p.first, qk = p.second;
		//printf("find node %d's %d-th son\n", u, qk);
		ans[qid] = cnt[dep[u] + qk] - 1;
	}
}

int main() {
	auto read = [](int & res) {
		int fh = 1; res = 0; char ch = getchar();
		for(; !isdigit(ch); ch = getchar()) if(ch == '-') fh = -1;
		for(; isdigit(ch); ch = getchar()) res = (res << 3) + (res << 1) + (ch ^ '0');
		res = res * fh; 
	};
	read(n); read(m);
	for(int i = 2; i <= n; ++i) {
		read(x); add(x, i), add(i, x);
	}
	dfs(1, 0), dfs1(1);
	exit(1);
	for(int i = 1; i <= m; ++i) read(x), read(y), qs[la(x, y)].push_back(std::make_pair(i, y));
	dfs4(1);
	for(int i = 1; i <= m; ++i) printf("%d ", ans[i]); 
	return 0; 
}