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