Eye-Pleasing City Park Tour

题意翻译

简要题意（太长所以还是挺多，请耐心看完）： 有一个城市公园形如一棵树，它的顶点是 $n$ 个景点，由 $n-1$ 条道路连接，第 $i$ 个景点有一个观赏值 $a_i$。每条道路都有一种颜色 $t_i$，如果 $t_i=0$ 则为黑色，$t_i=1$ 则为白色。同时公园里还配有黑白两种颜色的车。 Caropul 想乘车游览这个公园，但什么颜色的车走什么颜色的道路，想走另一种颜色的道路需要换一次车。 定义一次游览 $(u,v)$ 为走一条从 $u$ 景点开始，到 $v$ 景点结束的简单路径（即路径上的每个景点只能经过一次），$f(u,v)$ 为这条路径经过的所有景点（包括 $u,v$）的观赏值之和。 现在 Caropul 想知道对于所有不超过 $k$ 次**换车**的游览 $(u,v)$ ，$f(u,v)$ 的和对 $10^9+7$ 取模的结果，其中 $1\le u\le v\le n$。 **注意最开始上车不算一次换车。**

题目描述

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 $ .

输入输出样例

输入样例 #1

5 0
1 3 2 6 4
1 2 1
1 4 0
3 2 1
2 5 0

输出样例 #1

45

输入样例 #2

3 1
1 1 1
1 2 1
3 2 0

输出样例 #2

10