题目内容

小红拿到一棵 $n$ 个结点的树，第i个点的权值为 $a_i$ 。现在，你需要求解，对于全部的连通块，它们内部中结点权值为奇数的结点数量之和是多少。由于答案可能很大,请将答案对 $(10^9+7)$ 取模后输出。

她定义对于树上的两个点，如果它们相连，则称他们位于同一个连通块里。特别地，一个单独的点也可以构成一个连通块。连通块的大小即为连通块中节点的数量。

题解思路

本题是树形动态规划（Tree DP）的应用，目标是统计树上所有连通块中，节点权值为奇数的结点数量之和。树的结构保证了任何连通块都是一个子树的“子集”。我们可以通过对每个子树进行动态规划来解决这个问题。

设 $C[u]$ 表示以节点 $u$ 为根的子树的连通块数量（包括节点 $u$ 自身以及所有包含该节点的连通块）。我们可以通过子树的组合来递归地计算这个值。