526互联

CF1843D Apple Tree 题解

发布时间 2023-12-09 14:12:19作者: ShawyYum

题意：

思路：

树形 $ dp $ ：

设 $ cnt_u $ 表示以 $ u $ 为根的子树中叶子节点的数量，那么状态转移方程有：

当 $ u $ 为叶子节点时， $ cnt_u = 1 $ ；

当 $ u $ 不为叶子节点时， $ cnt_u = \sum_{i ∈ Son_u} cnt_{v_i} $ 。

对于每次查询， $ cnt_a \cdot cnt_b $ 即为最终答案。