#include "happy.h"
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define sz(x) (x).size()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define fi first
#define se second

using ll = long long;

const int N = 3e5 + 67;
const int M = 22;
vector<pair<int, int>> g[N];
int d[N];
bool is_act[N];
int cnt[2][M];

void dfs(int u, int p = -1) {
    for (pair<int, int> nxt: g[u]) {
        int v = nxt.fi;
        if (v != p) {
            d[v] = d[u] ^ nxt.se;
            dfs(v, u);
        }
    }
}

vector <ll> happy (int n, int q, vector <int> u, vector <int> v, vector <int> h, vector <int> tp, vector <int> l, vector <int> r) {
    for (int i = 0; i < n - 1; i++) {
        g[u[i]].pb({v[i], h[i]});
        g[v[i]].pb({u[i], h[i]});
        if (h[i] > 1) {
            check = 0;
        }
    }
    dfs(0);
    vector<ll> ans;
    ll curans = 0;
    for (int i = 0; i < q; i++) {
        if (tp[i] == 1) {
            for (int j = l[i]; j <= r[i]; j++) {
                if (is_act[j]) {
                    continue;
                }
                for (int k = 0; k < M; k++) {
                    int bt = (d[j] >> k) & 1;
                    curans += cnt[bt ^ 1][k];
                    cnt[bt][k]++;
                }
                is_act[j] = true;
            }
        } else {
            for (int j = l[i]; j <= r[i]; j++) {
                if (!is_act[j]) {
                    continue;
                }
                for (int k = 0; k < M; k++) {
                    int bt = (d[j] >> k) & 1;
                    curans -= cnt[bt ^ 1][k];
                    cnt[bt][k]--;
                }
                is_act[j] = false;
            }
        }
        ans.pb(curans);
    }
    return ans;
}
