考虑对于每个连通块，我们寻找一个代表元计数。
可以设定为深度最小的点，若深度同样小，则选定编号更小的。我们对于每个点 \(u\) 求出 \(l_u, r_u\) 表示根据上述比较规则下比 \(u\) 小，且距离不超过 \(C\)，最接近 \(u\) 的一左一右两个点。如果 \(l_u, r_u\) 任意一个点存在当前询问区间中则 \(u\) 不是代表元，所以统计 \(l_u < l \le u \le r < r_u\) 的 \(u\) 个数即可。
正确性只需证明非代表元的 \(l_u, r_u\) 一定有一个在 \([l, r]\) 中，反证，\(u\) 只和在上述比较规则小比他大的点 C - 连通，那么这些点一定也达到不了其他点，这与 \(u\) 是非代表元矛盾。
考虑点分治，按距离依次加入所有点，用线段树二分求出与某个位置最近的一左一右两个位置。最后做一个二维数点即可。
- 启示：设定代表元
点击查看代码
#include <bits/stdc++.h>
namespace Initial {
#define ll int
#define ull unsigned long long
#define fi first
#define se second
#define mkp make_pair
#define pir pair <ll, ll>
#define pb emplace_back
#define i128 __int128
using namespace std;
const ll maxn = 6e5 + 10, inf = 1e9, mod = 1e9 + 7;
ll power(ll a, ll b = mod - 2) {
ll s = 1;
while(b) {
if(b & 1) s = 1ll * s * a %mod;
a = 1ll * a * a %mod, b >>= 1;
} return s;
}
template <class T>
const ll pls(const T x, const T y) { return x + y >= mod? x + y - mod : x + y; }
template <class T>
void add(T &x, const T y) { x = x + y >= mod? x + y - mod : x + y; }
template <class T>
void chkmax(T &x, const T y) { x = x < y? y : x; }
template <class T>
void chkmin(T &x, const T y) { x = x > y? y : x; }
} using namespace Initial;
namespace IO {
char buf[1 << 22], *p1 = buf, *p2 = buf;
// #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, (1 << 22) - 10, stdin), p1 == p2)? EOF : *p1++)
template <class T>
void rd(T &x) {
char ch; bool f = 0;
while(!isdigit(ch = getchar()));
if(ch == '-') f = 1;
x = ch - '0';
while(isdigit(ch = getchar()))
x = (x << 1) + (x << 3) + ch - '0';
if(f) x = -x;
} char obuf[1 << 22], *O = obuf;
void putc(const char ch) { *O++ = ch; }
void write(ll x) {
if(x < 0) *O++ = '-', x = -x;
if(x > 9) write(x / 10);
*O++ = x % 10 + '0';
}
void write(const ll x, const char ch) { write(x), putc(ch); }
void flush() { fwrite(buf, O - buf, 1, stdout); }
} using IO::rd; using IO::write;
ll n, m, C, l[maxn], r[maxn], dep[maxn], id[maxn], w[maxn];
vector <ll> to[maxn];
void getdep(ll u, ll fa = 0) {
dep[u] = dep[fa] + 1;
for(ll v: to[u])
if(v ^ fa) getdep(v, u);
}
namespace centroid_divide {
struct SGT {
ll mn[maxn << 2];
const void modify(const ll p, const ll l, const ll r, const ll x) {
mn[p] = min(mn[p], w[x]); if(l == r) return;
const ll mid = l + r >> 1;
if(x <= mid) modify(p << 1, l, mid, x);
else modify(p << 1|1, mid + 1, r, x);
}
const ll queryl(const ll p, const ll l, const ll r, const ll x) {
if(l > x || mn[p] >= w[x]) return 0;
if(l == r) return l; const ll mid = l + r >> 1;
const ll c = queryl(p << 1|1, mid + 1, r, x);
if(c) return c;
return queryl(p << 1, l, mid, x);
}
const ll queryr(const ll p, const ll l, const ll r, const ll x) {
if(r < x || mn[p] >= w[x]) return n + 1;
if(l == r) return l; ll mid = l + r >> 1;
ll c = queryr(p << 1, l, mid, x);
if(c <= n) return c;
return queryr(p << 1|1, mid + 1, r, x);
}
const void clr(const ll p, const ll l, const ll r) {
if(mn[p] >= inf) return; mn[p] = inf;
if(l == r) return; ll mid = l + r >> 1;
clr(p << 1, l, mid), clr(p << 1|1, mid + 1, r);
}
} tr;
ll bs, rt, siz[maxn]; bool vis[maxn];
void findrt(ll u, ll N, ll fa = 0) {
siz[u] = 1; ll mx = 0;
for(ll v: to[u])
if(v != fa && !vis[v]) {
findrt(v, N, u), siz[u] += siz[v];
mx = max(mx, siz[v]);
} mx = max(mx, N - siz[u]);
if(mx < bs) bs = mx, rt = u;
} ll dis[maxn], len; pir vertice[maxn];
void dfs(ll u, ll fa = 0) {
siz[u] = 1, vertice[++len] = mkp(dis[u], u);
for(ll v: to[u])
if(v != fa && !vis[v]) {
dis[v] = dis[u] + 1, dfs(v, u);
siz[u] += siz[v];
}
}
void solve(ll u, ll N) {
bs = inf, findrt(u, N); len = 0;
vis[u = rt] = true, dis[u] = 0, dfs(u);
sort(vertice + 1, vertice + 1 + len), tr.clr(1, 1, n);
for(ll i = len, j = 1; i; i--) {
ll x = vertice[i].se, y;
while(j <= len && dis[y = vertice[j].se] + dis[x] <= C)
tr.modify(1, 1, n, y), ++j;
chkmax(l[x], tr.queryl(1, 1, n, x));
chkmin(r[x], tr.queryr(1, 1, n, x));
}
for(ll v: to[u])
if(!vis[v]) solve(v, siz[v]);
}
}
struct _BIT {
ll dat[maxn];
void add(ll x, ll v) {
for(; x <= n; x += x & -x) dat[x] += v;
}
ll ask(ll x) {
ll v = 0;
for(; x; x -= x & -x) v += dat[x];
return v;
}
} BIT; ll ans[maxn]; pir ff[maxn];
struct qur { ll l, r, id; } q[maxn];
int main() {
rd(n), rd(m), rd(C);
for(ll i = 2, x; i <= n; i++)
rd(x), to[x].pb(id[i] = i), to[i].pb(x); getdep(1);
sort(id + 1, id + 1 + n, [](ll x, ll y) {
return dep[x] ^ dep[y]? dep[x] < dep[y] : x < y;
});
for(ll i = 1; i <= n; i++) w[id[i]] = i;
for(ll i = 1; i <= n; i++) r[i] = n + 1;
centroid_divide::solve(1, n);
for(ll i = 1; i <= n; i++) ff[i] = mkp(r[i], l[i]);
sort(ff + 1, ff + 1 + n);
for(ll i = 1, l, r; i <= m; i++)
rd(q[i].l), rd(q[i].r), q[i].id = i;
sort(q + 1, q + 1 + m, [](const qur a, const qur b) {
return a.r < b.r;
});
for(ll i = 1, j = 0, k = 0; i <= n; i++) {
BIT.add(l[i] + 1, 1);
while(j < n && ff[j + 1].fi == i) BIT.add(ff[++j].se + 1, -1);
while(k < m && q[k + 1].r == i) ++k, ans[q[k].id] = BIT.ask(q[k].l);
} BIT = {};
sort(q + 1, q + 1 + m, [](const qur a, const qur b) {
return a.l < b.l;
});
for(ll i = 1, j = 0; i <= n; i++) {
while(j < m && q[j + 1].l == i)
++j, ans[q[j].id] -= BIT.ask(n - q[j].r + 1);
BIT.add(n - r[i] + 2, 1);
}
for(ll i = 1; i <= m; i++) printf("%d\n", ans[i]);
return 0;
}