#include "happy.h"
#include<bits/stdc++.h>
using namespace std;
vector<pair<int, int>> E[2009];
int dp[2009][2009];
bool open[2009];
void dfs(int a, int x, int y, int par){
    for (pair<int, int> i : E[x]){
        if (i.first == par)continue;
        dp[a][i.first] = (y ^ i.second);
        dfs(a, i.first, (y ^ i.second), x);
    }
}
vector<int> fnd(int s, int e, int par){
    if (s == e)return {e};
    for (auto i : E[s]){
        if (i.first == par)continue;
        vector<int> x = fnd(i.first, e, s);
        if (x.size()){
            x.push_back(s);
            return x;
        }
    }
}
vector<long long> ans;
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) {
    for (int i = 0; i < N - 1; i ++){
        E[u[i]].push_back({v[i], h[i]});
        E[v[i]].push_back({u[i], h[i]});
    }
    for (int i = 0; i < N; i ++){
        dfs(i, i, 0, 0);
    }
    long long total = 0;
    for (int q = 0; q < Q; q ++){
        vector<int> res = fnd(l[q], r[q], -1);
        if (t[q] == 1){
            for (int i = 0; i < res.size(); i ++){
                if (open[res[i]])continue;
                for (int j = 0; j < 2009; j ++){
                    if (open[j]){
                        total += dp[i][j];
                    }
                }
                open[i] = 1;
            }
        }
        if (t[q] == 2){
            for (int i = 0; i < res.size(); i ++){
                if (open[res[i]])continue;
                for (int j = 0; j < 2009; j ++){
                    if (open[j]){
                        total -= dp[i][j];
                    }
                }
                open[i] = 1;
            }
        }
        ans.push_back(total);
    }
    return ans;
}
