Bipartite Subtree Edge Addition

Given an undirected rooted tree with n nodes and root at node 1. For any node i, define \(f(i,k)\) as the number of ways to add k new edges inside the subtree rooted at i so that the resulting graph becomes bipartite. When adding edges, you are allowed to add an edge that already exists in the tree, but no two newly‐added edges can be identical.

To decide whether a selection of extra edges is valid, note that if you fix a bipartition for the subtree (by forcing the root i to be red and its descendants alternately blue and red), then any new edge must connect a red vertex and a blue vertex. In other words, if the numbers of red and blue vertices in the subtree (with i forced red) are \(r\) and \(b\) respectively, then the total number of possible new edges that can be safely added is \(m=r\times b\). Consequently, \(f(i,k)=\binom{m}{k}\), where the binomial coefficient is taken in standard form.

You are given an integer k, an array \(p\) such that for each node \(i\) you must output \(f(i,k) \bmod p_i\), and the tree itself. Note that the bipartition for the subtree rooted at any node i is defined in the natural way: force node i to be red, then every child gets the opposite color, and so on. If the global bipartite coloring (computed, say, from the given root 1) differs from the forced one at a node, simply swap the counts in that subtree.

Input Constraints and Clarifications:

• The first line contains two integers n and k.
• The second line contains n integers: \(p_1, p_2, \dots, p_n\).
• Each of the next n-1 lines contains two integers u and v indicating an edge between nodes u and v.

Output: Output n space separated integers, where the i-th integer is \(f(i,k) \bmod p_i\).

inputFormat

The first line contains two integers n and k (the number of nodes and the number of extra edges to add).

The second line contains n integers \(p_1, p_2, ..., p_n\) where each \(p_i\) is the modulus for node i.

Each of the next n - 1 lines contains two integers u and v describing an undirected edge between nodes u and v.

outputFormat

Output a single line containing n space-separated integers. The i-th integer should be \(f(i,k) \bmod p_i\) computed as \(\binom{r_i \times b_i}{k} \bmod p_i\), where \(r_i\) and \(b_i\) are the numbers of red and blue nodes respectively in the subtree rooted at i (with node i forced to be red).

sample

3 1
100 100 100
1 2
1 3

2 0 0