#include <bits/stdc++.h>

using namespace std;

const int N = (int)3e5 + 9;

vector < array < int, 2 > > g[N];

int a[N], t[21][N * 4][2], tt[N * 4], mo[N * 4];

void dfs(int v, int pr) {
    for (auto [u, c] : g[v]) {
        if (u == pr) continue;
        a[u] = a[v] ^ c;

        dfs(u, v);
    }
}

void build(int v, int vl, int vr) {
    if (vl == vr) {
        for (int i = 20; i >= 0; i--) {
            if ((a[vl] >> i) & 1) t[i][v][0]++;
        }

        return;
    }

    int vm = (vl + vr) / 2;
    build(v * 2, vl, vm);
    build(v * 2 + 1, vm + 1, vr);

    for (int i = 20; i >= 0; i--) t[i][v][0] = t[i][v * 2][0] + t[i][v * 2 + 1][0];
}

void push(int v, int vl, int vr) {
    if (mo[v] == 1) {
        tt[v] = (vr - vl + 1);

        for (int i = 0; i <= 20; i++) {
            t[i][v][1] = t[i][v][0];
            if (vl != vr) {
                mo[v * 2] = mo[v * 2 + 1] = 1;
            }
        }

        mo[v] = 0;
    } else if (mo[v] == 2) {
        for (int i = 0; i <= 20; i++) {
            t[i][v][1] = 0;
            if (vl != vr) {
                mo[v * 2] = mo[v * 2 + 1] = 2;
            }
        }

        tt[v] = 0;

        mo[v] = 0;
    }
}

void upd(int v, int vl, int vr, int l, int r, int val) {
    push(v, vl, vr);

    if (l <= vl && vr <= r) {
        mo[v] = val;
        push(v, vl, vr);

        return;
    }

    if (l > vr || vl > r) return;

    int vm = (vl + vr) / 2;
    upd(v * 2, vl, vm, l, r, val);
    upd(v * 2 + 1, vm + 1, vr, l, r, val);

    for (int i = 20; i >= 0; i--) t[i][v][1] = t[i][v * 2][1] + t[i][v * 2 + 1][1];
    tt[v] = tt[v * 2] + tt[v * 2 + 1];
}

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) {
    for (int i = 0; i < n - 1; i++) {
        g[u[i] + 1].push_back({v[i] + 1, h[i]});
        g[v[i] + 1].push_back({u[i] + 1, h[i]});
    }

    dfs(1, 1);
    build(1, 1, n);

    vector < long long > qq(q);

    for (int i = 0; i < q; i++) {
        int tip = T[i];

        if (tip == 1) {
            upd(1, 1, n, l[i] + 1, r[i] + 1, 1);
        } else upd(1, 1, n, l[i] + 1, r[i] + 1, 2);


        long long ans = 0;
        for (int i = 20; i >= 0; i--) {
            long long kol = t[i][1][1], kol2 = tt[1] - kol;

            ans += (kol * kol2) * (1ll << i);
        }

        qq[i] = ans;
    }

    return qq;
}
