A14497 | Eye-Pleasing City Park Tour

There is a city park represented as a tree with $n$ attractions as its vertices and $n - 1$ rails as its edges. The $i$ -th attraction has happiness value $a_i$ .

Each rail has a color. It is either black if $t_i = 0$ , or white if $t_i = 1$ . Black trains only operate on a black rail track, and white trains only operate on a white rail track. If you are previously on a black train and want to ride a white train, or you are previously on a white train and want to ride a black train, you need to use $1$ ticket.

The path of a tour must be a simple path — it must not visit an attraction more than once. You do not need a ticket the first time you board a train. You only have $k$ tickets, meaning you can only switch train types at most $k$ times. In particular, you do not need a ticket to go through a path consisting of one rail color.

Define $f(u, v)$ as the sum of happiness values of the attractions in the tour $(u, v)$ , which is a simple path that starts at the $u$ -th attraction and ends at the $v$ -th attraction. Find the sum of $f(u,v)$ for all valid tours $(u, v)$ ( $1 \leq u \leq v \leq n$ ) that does not need more than $k$ tickets, modulo $10^9 + 7$ .

The first line contains two integers $n$ and $k$ ( $2 \leq n \leq 2 \cdot 10^5$ , $0 \leq k \leq n-1$ ) — the number of attractions in the city park and the number of tickets you have.

The second line contains $n$ integers $a_1, a_2,\ldots, a_n$ ( $0 \leq a_i \leq 10^9$ ) — the happiness value of each attraction.

The $i$ -th of the next $n - 1$ lines contains three integers $u_i$ , $v_i$ , and $t_i$ ( $1 \leq u_i, v_i \leq n$ , $0 \leq t_i \leq 1$ ) — an edge between vertices $u_i$ and $v_i$ with color $t_i$ . The given edges form a tree.

Output an integer denoting the total happiness value for all valid tours $(u, v)$ ( $1 \leq u \leq v \leq n$ ), modulo $10^9 + 7$ .