#include "happy.h"
#include <bits/stdc++.h>
#define MAXN 2000

using namespace std;

struct edge{
    int to, pret;
};
vector <edge> graf[MAXN + 1];
int activ[MAXN + 1], viz[MAXN + 1];
long long sum[MAXN + 1][MAXN + 1];

void dfs(int start, int nod, int cur){
    int k, next;

//    printf("nod = %d, cur = %d\n", nod, cur);
    viz[nod] = 1;
    for(k = 0; k < graf[nod].size(); k++){
        if(!viz[graf[nod][k].to]){
            if(cur == -1){
                next = graf[nod][k].pret;
            }else{
                next = cur ^ graf[nod][k].pret;
            }
            sum[start][graf[nod][k].to] = next;
            sum[graf[nod][k].to][start] = next;
            dfs(start, graf[nod][k].to, next);
        }
    }
}

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){
    int i, j, x, y, k;

    vector <long long> rez;
    for(i = 0; i < N - 1; i++){
        graf[u[i]].push_back({v[i], h[i]});
        graf[v[i]].push_back({u[i], h[i]});
    }

//    printf("ok");
    for(i = 0; i < N; i++){
        for(j = 0; j <= N; j++){
            viz[j] = 0;
        }
        dfs(i, i, -1);
//        printf("sum[%d] = %d\n", i, sum[i]);
    }

    for(i = 0; i < Q; i++){
        if(t[i] == 1){
            for(j = l[i]; j <= r[i]; j++){
                activ[j] = 1;
            }
        }else{
            for(j = l[i]; j <= r[i]; j++){
                activ[j] = 0;
            }
        }

        rez.push_back(0);
        for(j = 0; j < N; j++){
            if(activ[j]){
//                printf("j = %d\n", j);
                for(k = j + 1; k < N; k++){
                    if(activ[k]){
                        rez[i] += sum[j][k];
//                        printf("k = %d, sum = %d\n", k, sum[j][k]);
                    }
                }
//                printf("\n");
            }
        }
//        printf("***\n");

    }
    return rez;
}
//6 5
//0 1 1
//1 2 2
//2 3 3
//2 4 4
//4 5 2
//
//1 1 2
//1 2 3
//2 2 2
//2 4 5
//1 0 5
