#include <bits/stdc++.h>

using namespace std;
using ll = long long;
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);
  for (ll i = 0; i < q; i++) {
    for (ll j = l[i]; j <= r[i]; j++) {
      if (t[i] == 1) {
        if (open[j]) continue;
        open[j] = 1;
        cntOpen++;
        for (ll k = 0; k < LG; k++) {
          if (col[j] & (1 << k)) {
            cnt[k]++;
            ans += (cntOpen - cnt[k]) * (1 << k);
          } else {
            ans += cnt[k] * (1 << k);
          }
        }
      } else {
        if (!open[j]) continue;
        open[j] = 0;
        cntOpen--;
        for (ll k = 0; k < LG; k++) {
          if (col[j] & (1 << k)) {
            cnt[k]--;
            ans -= (cntOpen - cnt[k]) * (1 << k);
          } else {
            ans -= cnt[k] * (1 << k);
          }
        }
      }
    }
    ret[i] = ans;
  }
  return ret;
}