#include <bits/stdc++.h>
using namespace std;
vector<long long> happy(int n, int q, vector<int> u, vector<int> v, vector<int> h, vector<int> t, vector<int> l, vector<int> r) {
    vector<vector<pair<int, long long>>> graph(n + 1);
    for (int i = 0; i < n - 1; i++) {
        graph[u[i]].push_back({v[i], h[i]});
        graph[v[i]].push_back({u[i], h[i]});
    }
    vector<vector<long long>> path(n + 1, vector<long long>(n + 1, -1));
    for (int i = 1; i <= n; i++) {
        path[i][i] = 0;
    }
    int s = 0;
    for (int i = 1; i <= n; i++) {
        if (graph[i].size() == 1) {
            s = i;
            break;
        }
    }
    queue<long long> qu;
    qu.push(s);
    while (!qu.empty()) {
        int u = qu.front();
        qu.pop();
        for (auto [v, w2] : graph[u]) {
            if (path[s][v] == -1) {
                path[s][v] = path[s][u] ^ w2;
                qu.push(v);
            }
        }
    }
    vector<long long> ans;
    vector<bool> stat(n + 1, 0);
    long long sum = 0;
    for (int i = 0; i < q; i++) {
        if (t[i] == 1) {
            for (int j = l[i]; j <= r[i]; j++) {
                if (stat[j] != 2 - t[j]) {
                    stat[j] = 2 - t[j];
                    for (int k = 1; k < j; k++) {
                        if (stat[k]) {
                            if (path[k][j] == -1) {
                                path[k][j] = path[s][k] ^ path[s][j];
                            }
                            sum += path[k][j];
                        }
                    }
                    for (int k = r[i] + 1; k <= n; k++) {
                        if (stat[k]) {
                            if (path[k][j] == -1) {
                                path[k][j] = path[s][k] ^ path[s][j];
                            }
                            sum += path[k][j];
                        }
                    }
                }
            }
        } else {
            for (int j = l[i]; j <= r[i]; j++) {
                if (stat[j] != 2 - t[j]) {
                    stat[j] = 2 - t[j];
                    for (int k = 1; k < j; k++) {
                        if (stat[k]) {
                            if (path[k][j] == -1) {
                                path[k][j] = path[s][k] ^ path[s][j];
                            }
                            sum -= path[k][j];
                        }
                    }
                    for (int k = r[i] + 1; k <= n; k++) {
                        if (stat[k]) {
                            if (path[k][j] == -1) {
                                path[k][j] = path[s][k] ^ path[s][j];
                            }
                            sum -= path[k][j];
                        }
                    }
                }
            }
        }
        ans.push_back(sum);
    }
    return ans;
}
