#include "happy.h"
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

vector <vector <pair <int, int>>> g;
vector <int> res;
vector <bool> used;

void dfs(int v, int x) {
  used[v] = 1;
  res[v] = x;
  for (auto [u, h] : g[v]) {
    if (!used[u]) {
      dfs(u, x ^ h);
    }
  }
}

std::vector <ll> happy(int n, int q,
                       std::vector <int> u, std::vector <int> v, std::vector <int> h,
                       std::vector <int> t, std::vector <int> l, std::vector <int> r) {
  g.resize(n);
  res.resize(n);
  used.resize(n);
  for (int i = 0; i < n-1; i++) {
    g[u[i]].emplace_back(v[i], h[i]);
    g[v[i]].emplace_back(u[i], h[i]);
  }
  dfs(0, 0);
  vector <ll> ans;
  vector <vector <int>> pref0(n, vector <int> (20));
  vector <vector <int>> pref1(n, vector <int> (20));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < 20; j++) {
      if (i > 0) pref0[i][j] = pref0[i-1][j];
      if (i > 0) pref1[i][j] = pref1[i-1][j];
      pref0[i][j] += (res[i] & (1 << j)) == 0;
      pref1[i][j] += (res[i] & (1 << j)) > 0;
    }
  }
  vector <int> cnt0(20), cnt1(20);
  for (int i = 0; i < q; i++) {
    if (t[i] == 1) {
      for (int j = 0; j < 20; j++) {
        cnt0[j] += pref0[r[i]][j] - (l[i] > 0 ? pref0[l[i] - 1][j] : 0);
        cnt1[j] += pref1[r[i]][j] - (l[i] > 0 ? pref1[l[i] - 1][j] : 0);
      }
    } else {
      for (int j = 0; j < 20; j++) {
        cnt0[j] -= pref0[r[i]][j] - (l[i] > 0 ? pref0[l[i] - 1][j] : 0);
        cnt1[j] -= pref1[r[i]][j] - (l[i] > 0 ? pref1[l[i] - 1][j] : 0);
      }
    }
    ll sum = 0;
    for (int j = 0; j < 20; j++) {
      sum += (1ll << j) * cnt0[j] * cnt1[j];
    }
    ans.push_back(sum);
  }
  return ans;
}
