#include "happy.h"
#include <vector>
#include <set>
#include <unordered_set>
#include <iostream>

using namespace std;
using ll = long long;

vector<vector<pair<ll, ll>>> g;
vector<vector<ll>> ud;

void dfs(ll v, ll p, ll xr, ll root) {
	ud[root][v] = xr;
	for (auto u : g[v]) {
		if (u.first != p) {
			dfs(u.first, v, (xr ^ u.second), root);
		}
	}
}

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) {
	g.resize(N);
	ud.resize(N, vector<ll>(N, 0));
	for (ll i = 0; i < N - 1; i++) {
		g[u[i]].push_back({ v[i], h[i] });
		g[v[i]].push_back({ u[i], h[i] });
	}
	unordered_set<int> st;
	for (ll i = 0; i < N; i++) {
		dfs(i, -1, 0, i);
	}
	vector<ll> ans(Q, 0);
	for (ll i = 0; i < Q; i++) {
		for (ll j = l[i]; j <= r[i]; j++) {
			if (t[i] == 1) {
				st.insert(j);
			}
			else {
				st.erase(j);
			}
		}
		vector<int> cur;
		for (auto q : st) {
			cur.push_back(q);
		}
		ll now = 0;
		for (ll fir = 0; fir < cur.size(); fir++) {
			for (ll sec = fir + 1; sec < cur.size(); sec++) {
				now += ud[cur[fir]][cur[sec]];
			}
		}
		ans[i] = now;
	}
	return ans;
}
