题目内容

小红有一棵树，每个节点上都有一个整数权值。她希望通过删除若干条边，将这棵树分割

为若干个连通块，使得每个连通块中所有节点的权值之和都是偶数。

题解

题目描述

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

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

注意：两种删除边的方案若删除的边集合不同，则视为不同的方案。结果对 $10^9+7$ 取模。