#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);
  auto get = [&](int u, int v) {
    return res[u] ^ res[v];
  };
  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 <bool> open(n);
  for (int i = 0; i < q; i++) {
    if (t[i] == 2) {
      for (int j = l[i]; j <= r[i]; j++) {
        open[j] = 0;
      }
    } else {
      for (int j = l[i]; j <= r[i]; j++) {
        open[j] = 1;
      }
    }
    ll sum = 0;
    for (int i = 0; i < 20; i++) {
      int cnt0 = 0;
      int cnt1 = 0;
      for (int u = 0; u < n; u++) {
        if (open[u]) {
          int x = (res[u] & (1 << i)) > 0;
          if (x) {
            sum += (1ll << i) * cnt0;
            cnt1++;
          } else {
            sum += (1ll << i) * cnt1;
            cnt0++;
          }
        }
      }
    }
    ans.push_back(sum);
  }
  return ans;
}
