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;
  int Size[200005];
  vector<pair<int, int> > v[200005];
  int forbid[200005];
  vector<int> tmp;
  void dfs(int first, int f) {
    Size[first] = 1;
    tmp.push_back(first);
    for (auto it : v[first]) {
      if (it.first != f && !forbid[it.first]) {
        dfs(it.first, first);
        Size[first] += Size[it.first];
      }
    }
  }
  int cen(int first) {
    tmp.clear();
    dfs(first, 0);
    int xx = Size[first];
    int res = 0;
    for (auto it : tmp) {
      if (Size[it] >= (xx + 1) / 2) {
        res = it;
      }
    }
    return res;
  }
  long long S[4][200005];
  const int mod = 1e9 + 7;
  void add(int first, int k, long long *s) {
    first++;
    for (int i = first; i < 200005; i += i & -i) {
      s[i] += k;
      s[i] %= mod;
    }
  }
  void reset(int first, long long *s) {
    first++;
    for (int i = first; i < 200005; i += i & -i) {
      s[i] = 0;
    }
  }
  long long query(int first, long long *s) {
    first++;
    long long res = 0;
    for (int i = first; i > 0; i -= i & -i) {
      res += s[i];
      res %= mod;
    }
    return res;
  }
  vector<pair<long long, long long> > vv;
  long long a[200005];
  void dfs(int first, int last, int f, int sum, long long sum2) {
    vv.push_back(make_pair(a[first] + sum2, sum));
    for (auto it : v[first]) {
      if (it.first != f && !forbid[it.first]) {
        dfs(it.first, it.second, first, sum + (it.second != last),
            (sum2 + a[first]) % mod);
      }
    }
  }
  long long ans = 0;
  int k;
  vector<pair<int, int> > ttmp;
  void go(int first) {
    first = cen(first);
    for (auto it : v[first]) {
      if (!forbid[it.first]) {
        dfs(it.first, it.second, first, 0, a[first]);
        for (auto it2 : vv) {
          ans += query(k - it2.second, S[it.second]);
          ans += query(k - it2.second, S[2 + it.second]) * it2.first % mod;
          ans += query(k - it2.second - 1, S[it.second ^ 1]);
          ans +=
              query(k - it2.second - 1, S[2 + (it.second ^ 1)]) * it2.first % mod;
          if (it2.second <= k) ans += it2.first;
          ans %= mod;
        }
        for (auto it2 : vv) {
          add(it2.second, it2.first - a[first], S[it.second]);
          add(it2.second, 1, S[2 + it.second]);
          ttmp.push_back(it2);
        }
        vv.clear();
      }
    }
    for (auto it : ttmp) {
      reset(it.second, S[0]);
      reset(it.second, S[1]);
      reset(it.second, S[2]);
      reset(it.second, S[3]);
    }
    ttmp.clear();
    forbid[first] = 1;
    for (auto it : v[first]) {
      if (!forbid[it.first]) {
        go(it.first);
      }
    }
  }
  void solve() {
    int n;
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]), ans += a[i];
    for (int i = 1; i < n; i++) {
      int first, second, w;
      scanf("%d %d %d", &first, &second, &w);
      v[first].push_back(make_pair(second, w));
      v[second].push_back(make_pair(first, w));
    }
    go(1);
    printf("%lld\n", (ans % mod + mod) % mod);
  }
  int main() {
    int t = 1;
    for (int i = 1; i <= t; i++) {
      solve();
    }
    return 0;
  }
  