308789: CF1575E. Eye-Pleasing City Park Tour

Memory Limit:512 MB Time Limit:4 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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

Input

题意翻译

简要题意(太长所以还是挺多,请耐心看完): 有一个城市公园形如一棵树,它的顶点是 $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$。 **注意最开始上车不算一次换车。**

加入题单

上一题 下一题 算法标签: