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 maxn = 200010, P = 1000000007;
  int n, K, rt, ans, lim;
  int a[maxn], sz[maxn], c[2][maxn], cs[2][maxn];
  bool solved[maxn];
  vector<pair<int, int>> G[maxn];
  void add(int *c, int p, int v) {
    for (p++; p <= lim; p += p & -p) {
      if ((c[p] += v) >= P) c[p] -= P;
    }
  }
  int query(int *c, int p) {
    int s = 0;
    for (p = min(lim, p + 1); p; p -= p & -p) {
      if ((s += c[p]) >= P) s -= P;
    }
    return s;
  }
  int main() {
    scanf("%d %d", &n, &K);
    for (int i = 1; i <= n; i++) {
      scanf("%d", &a[i]);
    }
    for (int i = 1, u, v, c; i < n; i++) {
      scanf("%d %d %d", &u, &v, &c);
      G[u].emplace_back(v, c), G[v].emplace_back(u, c);
    }
    function<void(int, int, int)> find_rt = [&](int v, int fa, int all) {
      sz[v] = 1;
      int mx = 0;
      for (auto &e : G[v]) {
        int u = e.first;
        if (u ^ fa && !solved[u]) {
          find_rt(u, v, all), sz[v] += sz[u];
          mx = max(mx, sz[u]);
        }
      }
      if (max(mx, all - sz[v]) * 2 <= all) rt = v;
    };
    function<void(int, int)> solve = [&](int v, int U) {
      solved[v] = 1;
      (ans += a[v]) %= P, lim = U;
      for (int col : {0, 1}) {
        fill(c[col], c[col] + lim + 1, 0);
        fill(cs[col], cs[col] + lim + 1, 0);
      }
      for (auto &e : G[v]) {
        int u = e.first;
        if (solved[u]) continue;
        vector<array<int, 2>> V;
        function<void(int, int, int, int, int)> dfs = [&](int x, int fa, int s,
                                                          int cnt, int lst) {
          sz[x] = 1;
          if (cnt <= K) {
            ans = (1LL * ans + a[v] + s) % P;
            V.push_back({cnt, s});
            for (int col : {0, 1}) {
              int rem = K - cnt - (col != e.second);
              if (rem < 0) continue;
              ans = (ans + 1LL * (a[v] + s) * query(c[col], rem)) % P;
              (ans += query(cs[col], rem)) %= P;
            }
          }
          for (auto &e : G[x])
            if (e.first ^ fa && !solved[e.first]) {
              dfs(e.first, x, (s + a[e.first]) % P, cnt + (e.second != lst),
                  e.second);
              sz[x] += sz[e.first];
            }
        };
        dfs(u, v, a[u], 0, e.second);
        for (auto &p : V) {
          add(c[e.second], p[0], 1);
          add(cs[e.second], p[0], p[1]);
        }
      }
      for (auto &e : G[v]) {
        int u = e.first;
        if (!solved[u]) find_rt(u, v, sz[u]), solve(rt, sz[u]);
      }
    };
    find_rt(1, 0, n), solve(rt, n);
    printf("%d\n", ans);
    return 0;
  }
  