1000ms

Difficulty: 3

算法与标签>DFS

会员或题库专享

请先，开通会员或购买题库保研机考题库，可解锁完整内容。

购买保研机考题库开通会员

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（保研机考题库），可解锁完整内容。

购买题库开通会员

题目思路

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

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

题目内容

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

输入描述

In following contests:

保研/考研模拟赛第一场|清华大学(深圳)|2022年保研夏令营上机笔试