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;
  mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
  mt19937 rnf(2106);
  const int N = 200005, M = 1000000007;
  int n, k;
  int a[N];
  vector<int> g[N], gc[N];
  bool c[N];
  int q[N];
  void dfs0(int x, int p) {
    q[x] = 1;
    for (int i = 0; i < g[x].size(); ++i) {
      int h = g[x][i];
      if (c[h]) continue;
      if (h == p) continue;
      dfs0(h, x);
      q[x] += q[h];
    }
  }
  int dfsc(int x, int p, int xx) {
    for (int i = 0; i < g[x].size(); ++i) {
      int h = g[x][i];
      if (c[h]) continue;
      if (h == p) continue;
      if (q[h] > q[xx] / 2) return dfsc(h, x, xx);
    }
    return x;
  }
  int s[N];
  void dfs1(int x, int p, int gg) {
    if (x == p)
      s[x] = a[x];
    else
      s[x] = (s[p] + a[x]) % M;
    for (int i = 0; i < g[x].size(); ++i) {
      int h = g[x][i];
      if (c[h]) continue;
      if (h == p) continue;
      if (gg != -1 && gc[x][i] != gg)
        q[h] = q[x] + 1;
      else
        q[h] = q[x];
      dfs1(h, x, gc[x][i]);
    }
  }
  vector<int> v;
  void dfs2(int x, int p) {
    v.push_back(x);
    for (int i = 0; i < g[x].size(); ++i) {
      int h = g[x][i];
      if (c[h]) continue;
      if (h == p) continue;
      dfs2(h, x);
    }
  }
  pair<int, int> t[2][N * 4];
  pair<int, int> mer(const pair<int, int>& a, const pair<int, int>& b) {
    return make_pair((a.first + b.first) % M, a.second + b.second);
  }
  void ubd(pair<int, int> t[], int tl, int tr, int x, int yf, int ys, int pos) {
    if (tl == tr) {
      t[pos].first = (t[pos].first + yf) % M;
      t[pos].second += ys;
      return;
    }
    int m = (tl + tr) / 2;
    if (x <= m)
      ubd(t, tl, m, x, yf, ys, pos * 2);
    else
      ubd(t, m + 1, tr, x, yf, ys, pos * 2 + 1);
    t[pos] = mer(t[pos * 2], t[pos * 2 + 1]);
  }
  pair<int, int> qry(pair<int, int> t[], int tl, int tr, int l, int r, int pos) {
    if (l > r) return make_pair(0, 0);
    if (tl == l && tr == r) return t[pos];
    int m = (tl + tr) / 2;
    return mer(qry(t, tl, m, l, min(m, r), pos * 2),
               qry(t, m + 1, tr, max(m + 1, l), r, pos * 2 + 1));
  }
  int ans;
  void solvv(int r) {
    q[r] = 0;
    dfs1(r, r, -1);
    ans = (ans + a[r]) % M;
    for (int i = 0; i < g[r].size(); ++i) {
      int x = g[r][i];
      if (c[x]) continue;
      int xc = gc[r][i];
      v.clear();
      dfs2(x, r);
      for (int i = 0; i < ((int)(v).size()); ++i) {
        int x = v[i];
        if (q[x] > k) continue;
        ans = (ans + s[x]) % M;
        pair<int, int> u = qry(t[xc], 0, k, 0, k - q[x], 1);
        ans = (ans + u.first) % M;
        ans = (ans + u.second * 1LL * (s[x] - a[r])) % M;
        u = qry(t[(xc ^ 1)], 0, k, 0, k - q[x] - 1, 1);
        ans = (ans + u.first) % M;
        ans = (ans + u.second * 1LL * (s[x] - a[r])) % M;
      }
      for (int i = 0; i < ((int)(v).size()); ++i) {
        int x = v[i];
        if (q[x] > k) continue;
        ubd(t[xc], 0, k, q[x], s[x], 1, 1);
      }
    }
    for (int i = 0; i < g[r].size(); ++i) {
      int x = g[r][i];
      if (c[x]) continue;
      int xc = gc[r][i];
      v.clear();
      dfs2(x, r);
      for (int i = 0; i < ((int)(v).size()); ++i) {
        int x = v[i];
        if (q[x] > k) continue;
        ubd(t[xc], 0, k, q[x], -s[x], -1, 1);
      }
    }
  }
  void solv() {
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 0; i < n - 1; ++i) {
      int x, y, z;
      cin >> x >> y >> z;
      g[x].push_back(y);
      g[y].push_back(x);
      gc[x].push_back(z);
      gc[y].push_back(z);
    }
    queue<int> q;
    q.push(1);
    while (!q.empty()) {
      int x = q.front();
      q.pop();
      dfs0(x, x);
      x = dfsc(x, x, x);
      solvv(x);
      for (int i = 0; i < g[x].size(); ++i) {
        int h = g[x][i];
        if (c[h]) continue;
        q.push(h);
      }
      c[x] = true;
    }
    ans = (ans + M) % M;
    cout << ans << "\n";
  }
  int main() {
    ios_base::sync_with_stdio(false), cin.tie(0);
    int tt = 1;
    while (tt--) solv();
    return 0;
  }
  