#include "happy.h"
#include <bitset>

struct node {
    int next;
    int val;
};

using paths = std::vector<node>;

std::vector<paths> tree;

std::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) {

    tree.resize(N+1);

    for (int i=0; i<N-1; i++) {
        tree[u[i]].push_back((node){v[i],h[i]});
        tree[v[i]].push_back((node){u[i],h[i]});
    }

    std::vector<int64_t> rez;
    std::vector<bool> mask(N);

    int nr = 0;
    for (int c=0; c<Q; c++) {
        for (int i=l[c]; i<=r[c]; i++) {
            if (t[c] == 1) {
                if (mask[i]) nr++;
                mask[i] = 0;
            }
            else {
                if (!mask[i]) nr--;
                mask[i] = 0;
            }
        }

        rez.push_back(nr * (nr+1) / 2);
    }

    return rez;
}