← 返回题目列表

Codeforces · 1575/E

E. 赏心悦目的城市公园之旅

中文机器翻译题面 查看原题

有一个城市公园,表示为一棵树,其顶点为 $$$n$$$ 景点,边缘为 $$$n - 1$$$ 铁轨。第 $$$i$$$ 个景点的幸福值为 $$$a_i$$$。

每个导轨都有一种颜色。如果 $$$t_i = 0$$$ 则为黑色,如果 $$$t_i = 1$$$ 则为白色。黑色列车仅在黑色铁轨上运行,白色列车仅在白色铁轨上运行。如果您以前乘坐过黑色火车,想乘坐白色火车,或者您以前乘坐过白色火车,想乘坐黑色火车,则需要使用 $$$1$$$ 车票。

游览的路径必须是简单的路径 - 不得多次访问某个景点。第一次登上火车时不需要车票。您只有 $$$k$$$ 车票,这意味着您最多只能转换 $$$k$$$ 次火车类型。特别是,您不需要车票即可通过由一种铁路颜色组成的路径。

将 $$$f(u, v)$$$ 定义为旅游 $$$(u, v)$$$ 中景点的幸福值总和,这是一条从第 $$$u$$$ 个景点开始,到第 $$$v$$$ 个景点结束的简单路径。求所有不需要超过 $$$k$$$ 门票的有效旅游 $$$(u, v)$$$ ($$$1 \leq u \leq v \leq n$$$) 的 $$$f(u,v)$$$ 总和,模 $$$10^9 + 7$$$。

输入

第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$, $$$0 \leq k \leq n-1$$$) — 城市公园的景点数量和您拥有的门票数量。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2,\ldots, a_n$$$ ($$$0 \leq a_i \leq 10^9$$$) — 每个景点的幸福值。

接下来的 $$$n - 1$$$ 行中的第 $$$i$$$ 包含三个整数 $$$u_i$$$、$$$v_i$$$ 和 $$$t_i$$$ ($$$1 \leq u_i, v_i \leq n$$$, $$$0 \leq t_i \leq 1$$$) — 之间的边顶点 $$$u_i$$$ 和 $$$v_i$$$ 颜色为 $$$t_i$$$。给定的边形成一棵树。

输出

输出一个整数,表示所有有效旅行 $$$(u, v)$$$ ($$$1 \leq u \leq v \leq n$$$) 的总幸福值,模 $$$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