线段树分裂求条

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define LL __int128
#define mid (l+r >> 1)
#define ls(o) t[o].l
#define rs(o) t[o].r

const int N = 3e5 + 5;
int n, m, dsu, dep[N], fa[N][22], bl[N], root[N], tot;
vector < int > G[N];

struct SegTree {
	int l, r, sum;
} t[N << 5];

void pushup(int o) { t[o].sum = t[ls(o)].sum + t[rs(o)].sum; }

int add(int o, int l, int r, int pos, int p) {
	if(!o) o = ++tot;
	if(l == r) { t[o].sum += p; return o; }
	if(pos <= mid) t[o].l = add(ls(o), l, mid, pos, p);
	else t[o].r = add(rs(o), mid+1, r, pos, p);
	pushup(o); return o;
}

int merge(int x, int y, int l, int r) {
//	printf("\nmerge in [%d %d] by %d %d\n", l, r, x, y);
	if(!x) return y; if(!y) return x;
	if(l == r) { t[x].sum += t[y].sum; return x; }
	int cur = ++tot;
	t[cur].l = merge(ls(x), ls(y), l, mid);
	t[cur].r = merge(rs(x), rs(y), mid+1, r);
	pushup(cur); return cur;
}

int query(int o, int l, int r, int pos) {
	if(!o) return 0;
	if(l == r) return t[o].sum;
	if(pos <= mid) return query(ls(o), l, mid, pos);
	return query(rs(o), mid+1, r, pos);
}

void dfs(int u, int fr) {
	dep[u] = dep[fr] + 1;
	fa[u][0] = fr;
	for(int i = 1; i < 21; i++) fa[u][i] = fa[fa[u][i-1]][i-1];
	for(int to : G[u]) if(to != fr) dfs(to, u);
}

int lca(int u, int k) {
	for(int i = 20; i >= 0; i--) 
		if(k & (1 << i)) u = fa[u][i];
	return u;
}

void getans(int u, int fr) {
//	printf("\n---now is in %d---\n", u);
	for(int to : G[u]) {
		if(to == fr) continue;
		getans(to, u);
		root[u] = merge(root[u], root[to], 1, n);
	}
	root[u] = add(root[u], 1, n, dep[u], 1);
}

int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) {
		int u; scanf("%d", &u);
		if(!u) bl[++dsu] = i;
		else {
			G[u].push_back(i);
			G[i].push_back(u);
		}
	}
	for(int i = 1; i <= dsu; i++) dfs(bl[i], 0);
	for(int i = 1; i <= dsu; i++) getans(bl[i], 0);
	
	scanf("%d", &m);
	while(m--) {
		int u, k; scanf("%d%d", &u, &k);
		int pos = lca(u, k);
//		printf("The LCA is %d\n", pos);
		if(!pos) printf("0 ");
		else printf("%d ", query(root[pos], 1, n, dep[u]) - 1);
	}
	return 0;
}