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;
  const int N = 2e5 + 10, M = N << 1, mod = 1e9 + 7;
  int n, k;
  int head[N], to[M], nxt[M], val[M], tot;
  bool st[N];
  pair<int, int> p1[N], p0[N];
  int pt0, pt1;
  long long tr0_cnt[N];
  long long tr1_cnt[N];
  long long tr0[N];
  long long tr1[N];
  int a[N];
  int lowbit(int first) { return first & (-first); }
  void update(long long tr[], int pos, long long dx) {
    pos++;
    for (int i = pos; i < N; i += lowbit(i)) {
      tr[i] = (tr[i] + dx) % mod;
    }
  }
  long long query(long long tr[], int pos) {
    pos++;
    long long res = 0;
    for (int i = pos; i; i -= lowbit(i)) {
      res += tr[i];
      res %= mod;
    }
    return res;
  }
  void add(int u, int v, int w) {
    nxt[++tot] = head[u];
    to[tot] = v;
    head[u] = tot;
    val[tot] = w;
  }
  int getsz(int u, int pre) {
    if (st[u]) return 0;
    int sum = 1;
    for (int i = head[u]; ~i; i = nxt[i]) {
      int j = to[i];
      if (j == pre) continue;
      sum += getsz(j, u);
    }
    return sum;
  }
  int getwc(int u, int pre, int tol, int &wc) {
    if (st[u]) return 0;
    int res = 1, ms = 0;
    for (int i = head[u]; ~i; i = nxt[i]) {
      int j = to[i];
      if (j == pre) continue;
      int t = getwc(j, u, tol, wc);
      res += t;
      ms = max(t, ms);
    }
    ms = max(ms, tol - res);
    if (ms <= tol / 2) wc = u;
    return res;
  }
  void dfs(int u, int pre, int cost, int last_edge, long long tolw,
           pair<int, int> p[], int &pt) {
    if (st[u]) return;
    if (cost <= k) p[++pt] = {cost, (tolw + a[u]) % mod};
    for (int i = head[u]; ~i; i = nxt[i]) {
      int j = to[i];
      if (j == pre) continue;
      dfs(j, u, cost + (last_edge == val[i] ? 0 : 1), val[i], (tolw + a[u]) % mod,
          p, pt);
    }
  }
  struct docu {
    int type;
    int pos;
    long long dx;
  };
  long long calc(int u) {
    if (st[u]) return 0;
    getwc(u, -1, getsz(u, -1), u);
    st[u] = 1;
    long long res = 0;
    vector<docu> temp;
    for (int i = head[u]; ~i; i = nxt[i]) {
      pt0 = 0, pt1 = 0;
      if (val[i])
        dfs(to[i], u, 0, val[i], 0, p1, pt1);
      else
        dfs(to[i], u, 0, val[i], 0, p0, pt0);
      for (int j = 1; j <= pt0; ++j) {
        res = (res + p0[j].second + a[u]) % mod;
        res = (res + query(tr0, k - p0[j].first)) % mod;
        res = (res + query(tr1, k - p0[j].first - 1)) % mod;
        res = (res + query(tr0_cnt, k - p0[j].first) * p0[j].second % mod) % mod;
        res = (res + query(tr1_cnt, k - p0[j].first - 1) * p0[j].second % mod) %
              mod;
      }
      for (int j = 1; j <= pt1; ++j) {
        res = ((res + p1[j].second) % mod + a[u]) % mod;
        res = (res + query(tr1, k - p1[j].first)) % mod;
        res = (res + query(tr0, k - p1[j].first - 1)) % mod;
        res = (res + query(tr1_cnt, k - p1[j].first) * p1[j].second % mod) % mod;
        res = (res + query(tr0_cnt, k - p1[j].first - 1) * p1[j].second % mod) %
              mod;
      }
      for (int j = 1; j <= pt0; ++j) {
        update(tr0, p0[j].first, p0[j].second + a[u]);
        temp.push_back({0, p0[j].first, p0[j].second + a[u]});
        update(tr0_cnt, p0[j].first, 1);
        temp.push_back({2, p0[j].first, 1});
      }
      for (int j = 1; j <= pt1; ++j) {
        update(tr1, p1[j].first, p1[j].second + a[u]);
        temp.push_back({1, p1[j].first, p1[j].second + a[u]});
        update(tr1_cnt, p1[j].first, 1);
        temp.push_back({3, p1[j].first, 1});
      }
    }
    for (auto &w : temp) {
      if (w.type == 0) {
        update(tr0, w.pos, -w.dx);
      } else if (w.type == 1) {
        update(tr1, w.pos, -w.dx);
      } else if (w.type == 2) {
        update(tr0_cnt, w.pos, -w.dx);
      } else {
        update(tr1_cnt, w.pos, -w.dx);
      }
    }
    for (int i = head[u]; ~i; i = nxt[i]) {
      int j = to[i];
      res = (res + calc(j)) % mod;
    }
    return res;
  }
  int main() {
    memset(head, -1, sizeof head);
    long long sum = 0;
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; ++i) {
      scanf("%d", &a[i]);
      sum = (sum + a[i]) % mod;
    }
    for (int i = 1; i < n; ++i) {
      int u, v, w;
      scanf("%d%d%d", &u, &v, &w);
      add(u, v, w);
      add(v, u, w);
    }
    printf("%lld", (calc(1) + sum) % mod);
    return 0;
  }
  