求助卡常

#include<bits/stdc++.h>
using namespace std;
inline int read() {
	int x = 0, f = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9') {
		if(ch == '-')	f = -1;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9') {
		x = (x << 3) + (x << 1) + ch - '0';
		ch = getchar();
	}
	return x * f;
}
int n, m, C, b[300005], head[300005], tail[600005], nxt[600005], tot, pre[300005], suf[300005], siz[300005];
inline void add_edge(int u, int v) {
	tail[++tot] = v;
	nxt[tot] = head[u];
	head[u] = tot;
	tail[++tot] = u;
	nxt[tot] = head[v];
	head[v] = tot;
	return;
}
int qB[300005], hB = 1, tB;
inline void bfs() {
	int bfn = 0;
	qB[++tB] = 1;
	b[1] = ++bfn;
	while(hB <= tB) {
		int p = qB[hB++];
		for(int i = head[p]; i; i = nxt[i]) {
			int ed = tail[i];
			if(b[ed])	continue;
			b[ed] = ++bfn;
			qB[++tB] = ed;
		}
	}
	return;
}
vector<int> rub;
bool flag[1500005];
	int val[1500005], Ans;
	bool isans;
	inline void pushup(int p) {
		val[p] = min(val[p << 1], val[p << 1 | 1]);
		return;
	}
	inline void build(int p, int l, int r) {
		val[p] = 1e9;
		if(l == r)	return;
		int mid = l + r >> 1;
		build(p << 1, l, mid);
		build(p << 1 | 1, mid + 1, r);
		return;
	}
	inline void ins(int p, int l, int r, int k, int x) {
		if(!flag[p])	rub.push_back(p);
		flag[p] = true;
		if(l == r) {
			val[p] = x;
			return;
		}
		int mid = l + r >> 1;
		if(k <= mid)	ins(p << 1, l, mid, k, x);
		else	ins(p << 1 | 1, mid + 1, r, k, x);
		pushup(p);
		return;
	}
	inline int ask1(int p, int l, int r, int x) {
		if(l == r)	return l;
		int mid = l + r >> 1;
		if(val[p << 1] <= x)	return ask1(p << 1, l, mid, x);
		return ask1(p << 1 | 1, mid + 1, r, x);
	}
	inline int ask2(int p, int l, int r, int x) {
		if(l == r)	return l;
		int mid = l + r >> 1;
		if(val[p << 1 | 1] <= x)	return ask2(p << 1 | 1, mid + 1, r, x);
		return ask2(p << 1, l, mid, x);
	}
	inline void query1(int p, int l, int r, int L, int R, int x) {
		if(L > R)	return;
		if(isans)	return;
		if(L <= l && r <= R) {
			if(val[p] > x)	return;
			isans = true;
			Ans = ask1(p, l, r, x);
			return; 
		}
		int mid = l + r >> 1;
		if(L <= mid)	query1(p << 1, l, mid, L, R, x);
		if(R > mid && !isans)	query1(p << 1 | 1, mid + 1, r, L, R, x);
		return;
	}
	inline void query2(int p, int l, int r, int L, int R, int x) {
		if(L > R)	return;
		if(isans)	return;
		if(L <= l && r <= R) {
			if(val[p] > x)	return;
			isans = true;
			Ans = ask2(p, l, r, x);
			return; 
		}
		int mid = l + r >> 1;
		if(R > mid)	query2(p << 1 | 1, mid + 1, r, L, R, x);
		if(L <= mid && !isans)	query2(p << 1, l, mid, L, R, x);
		return;
	}
	inline int Qpr(int id, int x) {
		isans = false;
		Ans = 0;
		query2(1, 1, n, 1, id - 1, x);
		return Ans;
	}
	inline int Qnx(int id, int x) {
		isans = false;
		Ans = n + 1;
		query1(1, 1, n, id + 1, n, x);
		return Ans;
	}
namespace Solve {
	int rt, mxsiz[300005], nowsiz, dis[300005];
	bool vis[300005];
	vector<int> vc;
	inline void getrt(int x, int fa) {
		mxsiz[x] = 0;
		siz[x] = 1;
		for(int i = head[x]; i; i = nxt[i]) {
			int ed = tail[i];
			if(ed == fa || vis[ed])	continue;
			getrt(ed, x);
			siz[x] += siz[ed];
			mxsiz[x] = max(mxsiz[x], siz[ed]);
		}
		mxsiz[x] = max(mxsiz[x], nowsiz - siz[x]);
		if(mxsiz[x] < mxsiz[rt])	rt = x;
		return;
	}
	inline void dfs(int x, int fa) {
		dis[x] = dis[fa] + 1;
		vc.push_back(x);
		for(int i = head[x]; i; i = nxt[i]) {
			int ed = tail[i];
			if(ed == fa || vis[ed])	continue;
			dfs(ed, x);
		}
		return;
	}
	inline bool cmp(int x, int y) {
		return b[x] < b[y];
	}
	inline void work(int x) {
		dis[0] = -1;
		vc.clear();
		dfs(x, 0);
		rub.clear();
		sort(vc.begin(), vc.end(), cmp); 
		for(auto id : vc) {
			pre[id] = max(pre[id], Qpr(id, C - dis[id]));
			suf[id] = min(suf[id], Qnx(id, C - dis[id]));
			if(dis[id] <= C)	ins(1, 1, n, id, dis[id]);
		}
		for(auto x : rub) {
			val[x] = 1e9;
			flag[x] = false;
		}
	//	cout<<endl;
		return;
	}
	inline void solve(int x) {
		if(nowsiz > 1)	work(x);
		vis[x] = true;
		int now = nowsiz;
//		cout<<x<<" "<<nowsiz<<endl; 
		for(int i = head[x]; i; i = nxt[i]) {
			int ed = tail[i];
			rt = 0;
			mxsiz[0] = 1e9;
			if(vis[ed])	continue;
			if(siz[ed] < siz[x])	nowsiz = siz[ed];
			else	nowsiz = now - siz[x];
			getrt(ed, x);
			solve(rt);
		}
		return;
	}
}
struct node {
	int l, r, id;
}que[600005];
int ans[600005], tr[300005];
inline int lowbit(int x) {
	return x & -x;
}
inline void add(int x, int y) {
	++x;
	while(x <= n + 2) {
		tr[x] += y;
		x += lowbit(x);
	}
	return;
}
inline int ask(int x) {
	++x;
	int res = 0;
	while(x) {
		res += tr[x];
		x -= lowbit(x);
	}
	return res;
}
vector<node> vc1[300005], vc2[300005];
vector<pair<int, int>> tag[300005];
int main() {
	n = read(); m = read(); C = read();
	for(int i = 1; i <= n; ++i) {
		pre[i] = 0; suf[i] = n + 1;
	}
	for(int i = 2; i <= n; ++i) {
		int fa = read();
		add_edge(fa, i);
	}
	bfs();
	Solve::rt = 0;
	Solve::nowsiz = n; 
	Solve::mxsiz[0] = 1e9;
	Solve::getrt(1, 0);
	build(1, 1, n);
	Solve::solve(Solve::rt);
//	for(int i = 1; i <= n; ++i)	cout<<pre[i]<<" "<<suf[i]<<endl;
	for(int i = 1; i <= m; ++i) {
		que[i].l = read(); que[i].r = read(); que[i].id = i;
		vc1[que[i].l].push_back(que[i]);
		vc2[que[i].r].push_back(que[i]);
	}
	for(int i = 1; i <= n; ++i) {
		tag[i].push_back(make_pair(i, 1));
		tag[suf[i]].push_back(make_pair(i, -1));
	}
	for(int i = 1; i <= n; ++i) {
		for(auto qu : vc1[i]) {
			ans[qu.id] -= ask(n + 1) - ask(qu.r);
		}
		add(suf[i], 1);
	}
	memset(tr, 0, sizeof tr);
	for(int i = 1; i <= n; ++i) {
		for(auto x : tag[i]) {
			if(x.second == 1)	add(pre[x.first], 1);
			else	add(pre[x.first], -1);
		}
		for(auto qu : vc2[i]) {
			ans[qu.id] += ask(qu.l - 1);
		}
	}
	for(int i = 1; i <= m; ++i) {
		printf("%d\n", ans[i]);
	}
	return 0;
}