#include "happy.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector<int>
#define pb push_back
#define pii pair<int,int>
#define ff first
#define ss second


vector<vector<pii>> adj;

int dfs(int u, int p, int d, int dest) {
    if(u == dest) return d;
    for(auto &[v, w] : adj[u]) {
        if(v != p) {
            return dfs(v, u, (w^(d == -1 ? w : d)), dest);
        }
    }
}

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) {
    adj.resize(N+1);
    for(int i = 0; i < N-1; i++) {
        adj[u[i]].pb({v[i], h[i]});
        adj[v[i]].pb({u[i], h[i]});
    }
    unordered_set<int> open;
    vector<ll int> ans;

    for(int i = 0; i < Q; i++) {
        for(int j = l[i]; j <= r[i]; j++) {
            if(t[i] == 1) {
                open.insert(j);
            } else open.erase(j);
        }
        ll sum = 0;
        for(auto it = open.begin(); it != open.end(); it++) {
            for(auto it2 = it; it2 != open.end(); it2++) {
                int dist = dfs(*it, *it, -1, *it2);
                sum += (dist);
            }
        }
        ans.pb(sum);
        
    }
    return ans;
}
