题解

题面描述

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

题目内容

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

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

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

输入描述

第一行给出一个整数 $n$ ，表示树的节点数。

第二行给出 $n$ 个整数 $w_1,w_2,...,w_n$ ，其中 $w_i$ 表示节点i的权值。

接下来 $n-1$ 行，每行包含两个整数 $u$ 与 $v(1≦u,v≦n,u≠v)$ ，表示节点 $u$ 与节点 $v$ 之间有一条边，保证给定的图构成一棵树。

$2 ≤n≤ 10^5$

$1 ≤w_i ≤10^9$

$1≤u,v≦n$

输出描述

输出 $n-1$ 个数，第 $i$ 个数表示删除 $i$ 条边后满足条件的方案数。

由于答案可能非常大，请对答案取模 $10^9 +7$ 后输出。

样例1

输入

5
1 2 3 4 4
1 2
1 3
2 4
2 5

输出

3 3 1 0

说明

当 $k=1$ 时，删除方案有 {$(1,2)$},{$(2,4)$},{$(2,5)$}，共 $3$ 种。

当 $k=2$ 时，删除方案有

{$(1, 2),(2,4)$},{$(1,2),(2,5)$},{$(2,5),(2,4)$}，共 $3$ 种。

当 $k=3$ 时，删除方案有{$(1,2),(2,4),(2,5)$}，共 $1$ 种。