#include "happy.h"
#include <bits/stdc++.h>
using namespace std;

vector<bool> viz{};
vector<vector<int>> prices{};
vector<vector<pair<int, int>>> graph{};

void dfs(int node, int parent, int current_price)
{
    viz[node] = true;
    prices[parent][node] = current_price;
    prices[node][parent] = current_price;
    for(auto child : graph[node])
    {
        if(!viz[child.first] /*&& prices[child.first][node] == -1 && prices[node][child.first] == -1*/)
        {
            current_price ^= child.second;
            dfs(child.first, parent, current_price);
            current_price ^= child.second;
        }
    }
}

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) 
{
    graph.resize(N, vector<pair<int, int>>{});
    prices.resize(N, vector<int>(N, -1));
    for(int i = 0; i < N - 1; i++)
    {
        graph[v[i]].emplace_back(u[i], h[i]);
        graph[u[i]].emplace_back(v[i], h[i]);
    }

    // precalculate sums
    for(int i = 0; i < N; i++)
    {
        viz.clear();
        viz.resize(N, false);
        dfs(i, i, 0);
    }

    long long curent = 0;
    vector<int> open(N, 0);
    vector<long long int> ans{};

    // for(int i = 0; i < N - 1; i++)
    // {
    //     for(int j = 0; j < N - 1; j++)
    //     {
    //         cout << prices[i][j] << " ";
    //     }
    //     cout << "\n";
    // }

    for(int i = 0; i < Q; i++)
    {
        if(t[i] == 1)
        {
            for(int j = l[i]; j <= r[i]; j++)
            {
                if(open[j] == false)
                {
                    open[j] = true;
                    for(int k = 0; k < N; k++)
                    {
                        if(open[k])
                        {
                            if(prices[k][j] != -1)
                                curent += prices[k][j];
                            else
                                curent += prices[j][k];
                        }
                    }
                }
            }
        }
        else
        {
            for(int j = l[i]; j <= r[i]; j++)
            {
                if(open[j] == true)
                {
                    open[j] = false;
                    for(int k = 0; k < N; k++)
                    {
                        if(open[k])
                        {
                            if(prices[k][j] != -1)
                                curent -= prices[k][j];
                            else
                                curent -= prices[j][k];
                        }
                    }
                }
            }
        }
        ans.emplace_back(curent);
    }
    return ans;
}
