CF1575E Eye-Pleasing City Park Tour

有一个城市公园，可以表示为一棵树，包含 $n$ 个景点作为顶点，$n-1$ 条铁轨作为边。第 $i$ 个景点有幸福值 $a_i$。 每条铁轨都有颜色。如果 $t_i=0$，则为黑色；如果 $t_i=1$，则为白色。黑色列车只能在黑色铁轨上行驶，白色列车只能在白色铁轨上行驶。如果你之前乘坐的是黑色列车，现在想换乘白色列车，或者之前乘坐的是白色列车，现在想换乘黑色列车，则需要使用 $1$ 张车票。 一次游览的路径必须是简单路径——不能重复经过同一个景点。第一次乘坐列车时不需要车票。你只有 $k$ 张车票，也就是说你最多只能换乘 $k$ 次不同颜色的列车。特别地，如果路径上所有铁轨颜色都相同，则不需要车票。 定义 $f(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 \times 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$ 行，每行包含三个整数 $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$ 取模。

由 ChatGPT 4.1 翻译