AISing Programming Contest 2021（AtCoder Beginner Contest 202）E.Count Descendants_snuke has a rooted tree with n vertices, numbered

题目链接

Problem Statement

We have a rooted tree with $N$ vertices, numbered $1,2,\dots ,N$.
Vertex 1 is the root, and the parent of Vertex $i(2\le i\le N)$ is Vertex $P_i$.
You are given $Q$ queries. In the $i$-th query $(1\le i\le Q)$, given integers $U_i$ and $D_i$, find the number of vertices u that satisfy all of the following conditions:

• Vertex $U_i$ is in the shortest path from u to the root (including the endpoints).
• There are exactly $D_i$ edges in the shortest path from u to the root.

Sample Input 1

7
1 1 2 2 4 2
4
1 2
7 2
4 1
5 5
1
2
3
4
5
6
7

Sample Output 1

3
1
0
0
1
2
3
4

思维+DFS~
一开始我想的是倍增判断祖先，然后对该高度的所有点一一判断，但是复杂度有 $O(n^{2}logn)$，显然不可取~
换个思维，我们可以记录一下时间戳，即 DFS 过程中进入某个点 $i$ 的时间 $in[i]$ 和离开某个点的时间 $out[i]$，则对他的的祖先 $j$ 而言，一定满足：
$$in[j]\le in[i]<out[j]$$
则我们可以记录每一层的 $in[i]$，对每次查询，在这一层二分找答案即可，AC代码如下：

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
int n, q, x, y, in[N], out[N], height[N], t = 0;
vector<int> depth[N], G[N];

void dfs(int u) {
    in[u] = t++;
    depth[height[u]].push_back(in[u]);
    for (auto v:G[u]) {
        height[v] = height[u] + 1;
        dfs(v);
    }
    out[u] = t++;
}

int main() {
    scanf("%d", &n);
    for (int i = 2; i <= n; i++) scanf("%d", &x), G[x].push_back(i);
    dfs(1);
    scanf("%d", &q);
    while (q--) {
        scanf("%d%d", &x, &y);
        int l = lower_bound(depth[y].begin(), depth[y].end(), in[x]) - depth[y].begin();
        int r = upper_bound(depth[y].begin(), depth[y].end(), out[x]) - depth[y].begin();
        printf("%d\n", r - l);
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31