题目思路

1.dfs预处理出 $dp_i$ 代表以点 $i$ 为根的子树的点的个数.容易发现转移方程

\large dp_i = \sum_{j是i的儿子} dp_j + 1

P1159. 2022年(深圳)保研夏令营机试题-第一题-树上计数

1000ms

難度: 3

算法与标签>DFS

给一棵 $N$ 个点的有根树，所有点从 $1$ 到 $N$ 标号，且以 $1$ 号点为根。问树上有多少个点满足其子树内（包含该点本身）的节点数大于等于 $L$ 且小于等于 $R$ 。

输入的第一行包含三个正整数 $N$ ， $L$ ， $R$ ，保证 $N\le 10^5 ， L \le R \le N$ 。

接下来的 $N一1$ 行，第 $i$ 行包含一个正整数 $f_{i+1}$ 表示点 $i + 1$ 的父亲节点编号。

输入保证合法。

输出一个正整数，表示对应的答案。

输入

输出

编辑器加载中…

输入

预期输出（选填）