#include "happy.h"
#include "bits/stdc++.h"
using namespace std;
#define pb push_back
#define ll long long
#define ls(v) (ll)v.size()
const ll N = 2005;
ll dp[N][N];
ll op[N];
vector<pair<ll, ll>> g[N];
void dfs(ll nd, ll p, ll r, ll x){
    dp[r][nd] = x;
    for(auto [val, it]:g[nd]){
        if(it != p){
            dfs(it, nd, r, x ^ val);
        }
    }
}
vector <long long int> happy (int N, int Q, vector <int> u, vector <int> v, vector <int> h, vector <int> t, vector <int> l, vector <int> r) {
    ll n, q;
    n = N;
    q = Q;
    for(ll i = 0;i<n-1;++i){
        g[u[i]].pb({h[i], v[i]});
        g[v[i]].pb({h[i], u[i]});
    }
    for(ll i = 0;i<n;++i) dfs(i, 0, i, 0);
    set<ll> op;
    ll ans = 0;
    vector<ll> answer;
    for(ll i = 0;i<q;++i){
        if(t[i] == 1){
            vector<ll> v;
            for(ll j = l[i];j<=r[i];++j){
                if(op.count(j) == 0){
                    v.pb(j);
                }
            }
            for(auto it:v){
                for(auto itt:op){
                    ans += dp[it][itt];
                }
            }
            for(ll i1 = 0;i1<ls(v);++i1){
                for(ll i2 = i1 + 1;i2<ls(v);++i2){
                    ans += dp[v[i1]][v[i2]];
                }
            }
            for(auto it:v) op.insert(it);
        }
        else{
            vector<ll> v;
            for(ll j = l[i];j<=r[i];++j){
                if(op.count(j) == 1){
                    v.pb(j);
                }
            }
            for(auto it:v){
                for(auto itt:op){
                    ans -= dp[it][itt];
                }
            }
            // for(ll i1 = 0;i1<ls(v);++i1){
            //     for(ll i2 = i1 + 1;i2<ls(v);++i2){
            //         ans -= dp[v[i1]][v[i2]];
            //     }
            // }
            for(auto it:v) op.erase(it);
        }
        answer.pb(ans);
    }
    return answer;
}
