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