
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include "happy.h"
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
using pii = pair<int, int>;
const ll inf = 2e9;
using namespace __gnu_pbds;
#define all(x) x.begin(), x.end()
template <class t> using oset = tree<t, null_type, less <t>, rb_tree_tag, tree_order_statistics_node_update>;
vector <vector<pii>> adj;
vector <bool> vis, open;
vector <vector<pii>> dp;
vector <int> d, p;
ll op = 0, curans = 0;
void dfs(ll v){
    vis[v] = 1;
    vector <vector<int>> pref(adj[v].size(), vector <int> (20)), suff = pref;
    for (auto &[x, w] : adj[v]){
        if (!vis[x]){
            p[x] = v;
            dfs(x);
            for (int i = 0 ; i < 20 ; i++){
                if (1LL << i & w){
                    swap(dp[x][i].first, dp[x][i].second);
                    dp[x][i].first += open[x];
                }
                else {
                    dp[x][i].second += open[x];
                }
                dp[v][i].first += dp[x][i].first;
                dp[v][i].second += dp[x][i].second;
            }
        }
    }
    for (int i = 0 ; i < adj[v].size(); i++){
        if (i == 0) {
            if (adj[v][i].first == p[v]) continue;
            for (int j = 0 ; j < 20 ; j++){
                pref[i][j] = dp[adj[v][i].first][j].second;
            }
        }
        else {
            for (int j = 0 ; j < 20 ; j++){
                pref[i][j] = dp[adj[v][i].first][j].second + pref[i - 1][j];
                if (adj[v][i].first == p[v]) pref[i][j] -= dp[adj[v][i].first][j].second;
            }
        }
    }
    for (int i = (int)adj[v].size() - 1 ; i >= 0 ; i--){
        if (i == (int)adj[v].size() - 1) {
            if (adj[v][i].first == p[v]) continue;
            for (int j = 0 ; j < 20 ; j++){
                suff[i][j] = dp[adj[v][i].first][j].second;
            }
        }
        else {
            for (int j = 0 ; j < 20 ; j++){
                suff[i][j] = dp[adj[v][i].first][j].second + suff[i + 1][j];
                if (adj[v][i].first == p[v]) suff[i][j] -= dp[adj[v][i].first][j].second;
            }
        }
    }
    for (int i = 0 ; i < adj[v].size() ; i++){
        if (adj[v][i].first == p[v]) continue;
        for (int j = 0 ; j < 20 ; j++){
            int sum = 0;
            if (i != 0){
                sum = pref[i - 1][j];
            }
            if (i != int(adj[v].size()) - 1){
                sum += suff[i + 1][j];
            }
            curans += sum * (1LL << j) * dp[adj[v][i].first][j].first;
        }
    }
    if (open[v]){
        for (int i = 0 ; i < 20 ; i++){
            curans += dp[v][i].first * (1LL << i);
        }
    }
}
ll findans(){
    vis.assign(vis.size(), 0);
    dp.assign(dp.size(), vector <pii> (20, make_pair(0, 0)));
    curans = 0;
    p.assign(p.size(), -1);
    dfs(0);
    return curans;
}
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){
    ll n = N, q = Q;
    open.resize(n);
    adj.resize(n);
    vis.resize(n);
    d.resize(n);
    p.resize(n, -1);
    dp.resize(n, vector <pii> (20));
    for (int i = 0 ; i < n - 1 ; i++){
        adj[v[i]].push_back({u[i], h[i]});
        adj[u[i]].push_back({v[i], h[i]});
    }
    vector <ll> ans;
    for (int i = 0 ; i < q ; i++){
        if (t[i] == 1){
            for (int j = l[i] ; j <= r[i] ; j++){
                open[j] = 1;
            }
        }
        else {
            for (int j = l[i] ; j <= r[i] ; j++){
                open[j] = 0;
            }
        }
        ans.emplace_back(findans());
    }
    return ans;
}
