题目内容

小红有一棵树，每个节点上都有一个整数权值。她希望通过删除若干条边，将这棵树分割为若干个连通块，使得每个连通块中所有节点的权值之和都是偶数。

请你求出，对于每个 $k(1≦k≦n-1)$ ，删除 $k$ 条边后得到的 $k+1$ 个连通块满足条件的方案数。如果不存在满足条件的方案，对应的答案记为 $0$ 。

注意：两种删除边的方案若删除的边集合不同，则视为不同的方案。

题解

题面描述

给定一棵有 $n$ 个节点的树，每个节点上都有一个整数权值 $w_i$。小红希望删除若干条边，将这棵树分割成若干个连通块，并要求每个连通块中所有节点权值之和均为偶数。
要求对于每个 $k$，统计删除 $k$ 条边后得到的 $k+1$ 个连通块都满足条件的方案数（两组边集合不同视为不同方案），若不存在则答案记为 $0$。
最后答案对 $10^9+7$ 取模输出。