#include <bits/stdc++.h>

using namespace std;
using ll = long long;

struct SegTree {
  struct Node {
    int x;
  };
  Node merge(Node n1, Node n2) {
    return {n1.x + n2.x};
  }
  vector<Node> t;
  void upd(int v, int l, int r, int j, int x) {
    if (r - l <= 1) {
      t[v] = {x};
      return;
    }
    int m = (l + r) / 2;
    if (j < m) {
      upd(v * 2 + 1, l, m, j, x);
    } else {
      upd(v * 2 + 2, m, r, j, x);
    }
    t[v] = merge(t[2 * v + 1], t[2 * v + 2]);
  }

  Node get(int v, int l, int r, int ql, int qr) {
    if (l >= ql && r <= qr) {
      return t[v];
    }
    if (l >= qr || r  <= ql) return {0};
    int m = (l + r) / 2;
    return merge(get(2 * v + 1, l, m, ql, qr), get(2 * v + 2, m, r, ql, qr));
  }
};


vector<vector<pair<ll, ll>>> g;
vector<ll> col; // mask
const ll LG = 21;
void dfs1(ll v, ll c, ll p) {
  col[v] = c;
  for (auto [u, h] : g[v]) {
    if (u == p) continue;
    dfs1(u, c ^ h, v);
  }
}

vector <long long int> happy (int n, int q, vector <int> u,
  vector <int> v, vector <int> h, vector <int> t, vector <int> l, vector <int> r) {
  g.resize(n);
  col.resize(n);
  for (ll i = 0; i < n - 1; i++) {
    g[v[i]].emplace_back(u[i], h[i]);
    g[u[i]].emplace_back(v[i], h[i]);
  }
  dfs1(0, 0, -1);
  vector<ll> cnt(LG, 0); // col[j] = 1
  ll ans = 0;
  ll cntOpen = 0;
  vector<ll> ret(q);
  vector<bool> open(n, 0);
  vector<SegTree> a(LG);
  for (int i = 0; i < LG; i++) {
    a[i].t.resize(4 * n, {0});
    for (int j = 0; j < n; j++) {
      if ((1 << i) & col[j]) {
        a[i].upd(0, 0, n, j, 1);
      }
    }
  }
  for (ll i = 0; i < q; i++) {
    for (ll k = 0; k < LG; k++) {
      if (t[i] == 1) {
        int cntGood = a[k].get(0, 0, n, l[i], r[i] + 1).x;
        int cntOth = r[i] - l[i] + 1 - cntGood;
        int cntGoodOut = cnt[k];
        int cntOthOut = cntOpen - cnt[k];
        ans += (cntGood * cntOth + cntGood * cntOthOut + cntOth * cntGoodOut) * (1 << k);
        cnt[k] += cntGood;
        cntOpen += (r[i] - l[i] + 1);

      } else {
        int cntGood = a[k].get(0, 0, n, l[i], r[i] + 1).x;
        int cntOth = r[i] - l[i] + 1 - cntGood;
        int cntGoodOut = cnt[k];
        int cntOthOut = cntOpen - cnt[k];
        ans -= (cntGood * cntOth + cntGood * cntOthOut + cntOth * cntGoodOut) * (1 << k);
        cnt[k] -= cntGood;
        cntOpen -= (r[i] - l[i] + 1);
      }
    }
    ret[i] = ans;
  }
  return ret;
}