#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];
int pr[2][M][N];

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]});
    }
    dfs(0);
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < M; j++) {
            int bt = (d[i - 1] >> j) & 1;
            pr[bt ^ 1][j][i] = pr[bt ^ 1][j][i - 1];
            pr[bt][j][i] = pr[bt][j][i - 1] + 1;
        }
    }
    vector<ll> ans;
    for (int i = 0; i < q; i++) {
        ll curans = 0;
        if (tp[i] == 1) {
            for (int j = 0; j < M; j++) {
                cnt[0][j] += pr[0][j][r[i] + 1] - pr[0][j][l[i]];
                cnt[1][j] += pr[1][j][r[i] + 1] - pr[1][j][l[i]];
                ll pr = 1LL * cnt[0][j] * cnt[1][j] << j;
                curans += pr;
            }
        } else {
            for (int j = 0; j < M; j++) {
                cnt[0][j] -= pr[0][j][r[i] + 1] - pr[0][j][l[i]];
                cnt[1][j] -= pr[1][j][r[i] + 1] - pr[1][j][l[i]];
                ll pr = 1LL * cnt[0][j] * cnt[1][j] << j;
                curans += pr;
            }
        }
        ans.pb(curans);
    }
    return ans;
}
