[AtCoder Beginner Contest 202] E - Count Descendants

[Wizmann]

题意

一个N个节点的树，节点1为根。

给定Q个查询<Ui, Di>，问有多少个节点v满足以下条件：

• 从节点v到根的路径上，一定包含节点Ui
• 节点v的深度为Di

数据规模：

• 2 <= N <= 2 * 10^5
• 1 <= Q <= 2 * 10^5
• 所有数据都合法

Problem

解法

对于单独的查询，如果Ui是根，题目会非常简单。统计深度为Di的节点的数目即可。（有手就行的DFS）

这里考虑换根DP（误

这里采用一种”差分DP“，借鉴了换根DP的思路。

因为节点的深度Di是从根出发的绝对深度，所以我们使用depth[]数组记录在某一深度有多少个节点即可。

然后需要考虑如何”换根“，才能使得depth[]数组能表示以节点v为根的子树，在不同深度上的节点数。

首先将查询离线化处理，将查询按Ui进行索引。

使用DFS统计各个深度的节点的个数depth[]。假设DFS到节点v，节点v有若干子节点。当我们未统计子节点时，depth数组中已经包含了一些信息，而这些信息属于其它的子树，并不需要被记录到关于当前节点的查询中。

所以我们使用差分的方法，在DFS子树之前先遍历关于v的查询，在ans[]数组中将已有的记录减掉。在DFS返回v节点时，再加上depth[]中的信息。二者之差，就是以v节点为根的子树中所求的答案。

Code