#include "happy.h"
#include <iostream>
#include <iomanip>
#include <vector>
#include <set>
#include <array>

using namespace std;
const int N = 3e5 + 67;
const int LOG = 22;
typedef long long ll;

int n, q;
int pref_xor[N];

#define ff first
#define ss second

vector<pair<int, long long>>G[N];

void dfs(int node, int parent)
{
	for (auto i : G[node])
	{
		if (i.ff == parent)continue;
		pref_xor[i.ff] = pref_xor[node] ^ i.ss;
		dfs(i.ff, node);
	}
}

array<int, LOG>pref[N];

array<int, LOG>hanac(array<int, LOG>a, array<int, LOG>b)
{
	for (int i = 0; i < LOG; i++)
		a[i] -= b[i];
	return a;
}

array<int, LOG>gumar(array<int, LOG>a, array<int, LOG>b)
{
	for (int i = 0; i < LOG; i++)
		a[i] += b[i];
	return a;
}

array<int, LOG>nul;

struct S
{
	struct node
	{
		array<int, LOG>ar;
		int lazy;
		int cnt;
	}null = {nul, -1, 0};

	// -1 aseliq chuni
	// 0 hanac
	// 1 gumar 

	int n;

	vector<node>t;
	void init(int _n)
	{
		n = _n;
		t.assign(4 * n, null);
	}

	void push(int x, int lx, int rx)
	{
		if (lx == rx || t[x].lazy == -1)
			return;
		int mid = (lx + rx) / 2;
		t[2 * x].lazy = t[x].lazy;
		t[2 * x + 1].lazy = t[x].lazy;
		if (t[x].lazy)
		{
			t[2 * x].ar = hanac(pref[mid], pref[lx - 1]);
			t[2 * x + 1].ar = hanac(pref[rx], pref[mid]);
			t[2 * x].cnt = (mid - lx + 1);
			t[2 * x + 1].cnt = (rx - mid);
		}
		else
		{
			t[2 * x].ar = nul;
			t[2 * x + 1].ar = nul;
			t[2 * x].cnt = 0;
			t[2 * x + 1].cnt = 0;
		}
		t[x].lazy = -1;
	}


	void update(int x, int lx, int rx, int l, int r, bool type)
	{
		if (lx > r || rx < l)
			return;
		if (lx >= l && rx <= r)
		{
			if (type)
				t[x] = { hanac(pref[rx], pref[lx - 1]), type, type * (rx - lx + 1) };
			else
				t[x] = { nul, type, type * (rx - lx + 1) };
			return;
		}
		push(x, lx, rx);
		int mid = (lx + rx) / 2;
		update(2 * x, lx, mid, l, r, type);
		update(2 * x + 1, mid + 1, rx, l, r, type);
		t[x].ar = gumar(t[2 * x].ar, t[2 * x + 1].ar);
		t[x].cnt = t[2 * x].cnt + t[2 * x + 1].cnt;
	}
}segTree;

array<int, LOG>f(int x)
{
	array<int, LOG>a = nul;
	for (int i = 0; i < LOG; i++)
		if (x & (1 << i))
			a[i] = 1;
	return a;
}

std::vector <long long int> 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) {
	n = N;
	q = Q;
	for (int i = 0; i < LOG; i++)
		nul[i] = 0;
	vector<ll>ans;
	for (int i = 0; i < n - 1; i++)
	{
		G[u[i]].push_back({ v[i], h[i] });
		G[v[i]].push_back({ u[i], h[i] });
	}
	segTree.init(n);
	dfs(0, -1);
	pref[0] = nul;
	for (int i = 1; i < n; i++)
	{
		pref[i] = gumar(pref[i - 1], f(pref_xor[i]));
	}

	for (int i = 0; i < q; i++)
	{
		int s = t[i];
		int L = l[i];
		int R = r[i];
		if (s == 1)
		{
			segTree.update(1, 0, n - 1, L, R, 1);
		}
		else
		{
			segTree.update(1, 0, n - 1, L, R, 0);
		}

		ll answer = 0;
		
		S::node H = segTree.t[1];
		for (int b = 0; b < LOG; b++)
		{
			answer += (1ll << b) * (H.ar[b]) * (H.cnt - H.ar[b]);
		}
		ans.push_back(answer);
	}
	return ans;
}
