题解

题目描述

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

请你求出，对每个 $k\ (1 \le k \le n-1)$，删除 $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$种。