#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int MAXN = 3e5;
const int MAXL = 20;

vector <pair <int, int>> g[MAXN + 5];
ll brodd[MAXN + 5][MAXL + 5];
ll breven[MAXN + 5][MAXL + 5];
bool f[MAXN + 5];

ll ans = 0;

void dfs(int u, int p) {
    for (auto [v, w] : g[u]) {
        if (v == p) continue;
        dfs(v, u);
        for (int bit = 0; bit < MAXL; bit++) {
            if ((1 << bit) & w) {
                brodd[u][bit] += breven[v][bit] + f[v];
                breven[u][bit] += brodd[v][bit];
            }
            else {
                brodd[u][bit] += brodd[v][bit];
                breven[u][bit] += breven[v][bit] + f[v];
            }

        }
    }
}

void dfs_solve(int u, int p, const vector <int> &broddup, const vector <int> &brevenup) {
    if (f[u]) {
        for (int bit = 0; bit < MAXL; bit++) {
            ans += broddup[bit] * (1 << bit);
            ans += brodd[u][bit] * (1 << bit);
        }
    }
    for (int bit = 0; bit < MAXL; bit++) {
        ///cout << u << " " << bit << " " << brevenup[bit] << " " << broddup[bit] << endl;
    }
    for (auto [v, w] : g[u]) {
        if (v == p) continue;
        vector <int> nweven(MAXL + 1), nwodd(MAXL + 1);
        for (int bit = 0; bit < MAXL; bit++) {
            if ((1 << bit) & w) {
                nweven[bit] = broddup[bit] + brodd[u][bit] - breven[v][bit] - f[u];
                nwodd[bit] = brevenup[bit] + f[u] + breven[u][bit] - brodd[v][bit];
            }
            else {
                nweven[bit] = brevenup[bit] + breven[u][bit] - breven[v][bit];
                nwodd[bit] = broddup[bit] + brodd[u][bit] - brodd[v][bit];
            }
        }
        dfs_solve(v, u, nwodd, nweven);
    }
}

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) {
   // cout << "entered" << endl;
    int n = N, q = Q;
    for (int i = 0; i < n - 1; i++) {
        g[u[i]].push_back({v[i], h[i]});
        g[v[i]].push_back({u[i], h[i]});
    }
    vector <int> base(MAXL + 1);
    vector <ll> ret;
    for (int i = 0; i < q; i++) {
        int type = t[i];
        for (int j = l[i]; j <= r[i]; j++) {
            f[j] = (type - 1) ^ 1;
        }
        for (int j = 0; j < n; j++) {
            for (int bit = 0; bit < MAXL; bit++) {
                brodd[j][bit] = breven[j][bit] = 0;
            }
        }
        dfs(0, -1);
        ans = 0;
        dfs_solve(0, -1, base, base);
        ret.push_back(ans);
        ///cout << endl;
    }
    return ret;
}
