description: 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 ≤ u ≤ v ≤ n) that does not need more than k tickets, modulo 10^9 + 7.
  
  Input
  
  The first line contains two integers n and k (2 ≤ n ≤ 2 ⋅ 10^5, 0 ≤ k ≤ 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,…, a_n (0 ≤ a_i ≤ 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 ≤ u_i, v_i ≤ n, 0 ≤ t_i ≤ 1) — an edge between vertices u_i and v_i with color t_i. The given edges form a tree.
  
  Output
  
  Output an integer denoting the total happiness value for all valid tours (u, v) (1 ≤ u ≤ v ≤ n), modulo 10^9 + 7.
  
  Examples
  
  Input
  
  
  5 0
  1 3 2 6 4
  1 2 1
  1 4 0
  3 2 1
  2 5 0
  
  
  Output
  
  
  45
  
  
  Input
  
  
  3 1
  1 1 1
  1 2 1
  3 2 0
  
  
  Output
  
  
  10
solution: #include <bits/stdc++.h>
  using namespace std;
  void abc() { cout << endl; }
  template <typename T, typename... U>
  void abc(T a, U... b) {
    cout << a << ' ', abc(b...);
  }
  template <typename T>
  void printv(T l, T r) {
    while (l != r) cout << *l << " \n"[++l == r];
  }
  template <typename A, typename B>
  istream& operator>>(istream& o, pair<A, B>& a) {
    return o >> a.first >> a.second;
  }
  template <typename A, typename B>
  ostream& operator<<(ostream& o, pair<A, B> a) {
    return o << '(' << a.first << ", " << a.second << ')';
  }
  template <typename T>
  ostream& operator<<(ostream& o, vector<T> a) {
    bool is = false;
    for (T i : a) {
      o << (is ? ' ' : '{'), is = true, o << i;
    }
    return o << '}';
  }
  template <typename T>
  struct vv : vector<vector<T>> {
    vv(int n, int m, T v) : vector<vector<T>>(n, vector<T>(m, v)) {}
    vv() {}
  };
  template <typename T>
  struct vvv : vector<vv<T>> {
    vvv(int n, int m, int k, T v) : vector<vv<T>>(n, vv<T>(m, k, v)) {}
    vvv() {}
  };
  const int mod = 1e9 + 7, N = 200087, logN = 20, K = 111;
  vector<pair<int, int>> adj[N];
  vector<int> a;
  int sz[N], k;
  bool vis[N];
  void dfs_sz(int v, int pa) {
    sz[v] = 1;
    for (auto [u, t] : adj[v])
      if (u != pa && !vis[u]) {
        dfs_sz(u, v);
        sz[v] += sz[u];
      }
  }
  int dfs_cen(int v, int pa, int n) {
    for (auto [u, t] : adj[v])
      if (u != pa && !vis[u] && sz[u] > n / 2) {
        return dfs_cen(u, v, n);
      }
    return v;
  }
  long long int sum[N], chg[N];
  long long int val[N][4];
  vector<int> mov[4];
  void add(int p, long long int v, int t) {
    p++;
    for (int i = p; i < N; i += i & (-i))
      (val[i][t] += v) %= mod, mov[t].push_back(i);
  }
  long long int query(int p, int t) {
    p++;
    long long int ans = 0;
    for (int i = p; i > 0; i -= i & (-i)) {
      (ans += val[i][t]) %= mod;
    }
    return ans;
  }
  void rollback(int t) {
    while (!mov[t].empty()) {
      val[mov[t].back()][t] = 0, mov[t].pop_back();
    }
  }
  vector<int> now;
  long long int ans = 0;
  void dfs_ans(int v, int pa, int cc, int c) {
    if (~pa) now.push_back(v);
    sum[v] = ((~pa ? sum[pa] : 0) + a[v]) % mod;
    for (auto [u, t] : adj[v])
      if (u != pa && !vis[u]) {
        chg[u] = chg[v] + (!~pa ? 0 : (cc != t));
        dfs_ans(u, v, t, c);
        if (!~pa) {
          for (int v : now) {
            if (chg[v] <= k) (ans += sum[v]) %= mod;
            (ans += query(k - chg[v], t) +
                    query(k - chg[v], t | 2) * (sum[v] + mod - a[c]) % mod) %=
                mod;
            (ans += query(k - chg[v] - 1, t ^ 1) +
                    query(k - chg[v] - 1, (t ^ 1) | 2) * (sum[v] + mod - a[c]) %
                        mod) %= mod;
          }
          for (int v : now) {
            add(chg[v], sum[v], t);
            add(chg[v], 1, t | 2);
          }
          now.clear();
        }
      }
  }
  void dfs_cd(int v, int pa) {
    dfs_sz(v, pa);
    int c = dfs_cen(v, pa, sz[v]);
    vis[c] = true;
    chg[c] = 0;
    dfs_ans(c, -1, -1, c);
    rollback(0), rollback(1), rollback(2), rollback(3);
    for (auto [u, t] : adj[c])
      if (!vis[u]) {
        dfs_cd(u, c);
      }
  }
  int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n >> k;
    a.resize(n);
    for (int i = 0; i < n; ++i) cin >> a[i], (ans += a[i]) %= mod;
    for (int i = 0, u, v, t; i < n - 1; ++i) {
      cin >> u >> v >> t, --u, --v;
      adj[u].emplace_back(v, t);
      adj[v].emplace_back(u, t);
    }
    dfs_cd(0, -1);
    cout << ans << endl;
  }
  