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

vector<int> xorSum;

const int STsize = 8;

struct ST
{
    ll sum = 0;
    int size = 0;
    int Allpot[20];
    int pot[20]; //powers of two
    int lazy = 0;// 0 - nothing, 1 - make all, -1 - deleate all
    int fullSize;
    ll fullSum;
    int l;
    int r; // [)
};

ST STree[2*STsize];

void applay(int i){
    if((i<STsize) && (STree[i].lazy)){
        STree[2*i].lazy = STree[i].lazy;
        STree[2*i+1].lazy = STree[i].lazy;
    }
    if (STree[i].lazy == 1){
        STree[i].lazy = 0;
        for (int j = 0; j < 20; j++)
        {
            STree[i].pot[j] = STree[i].Allpot[j];
        }STree[i].size = STree[i].fullSize;
        STree[i].sum = STree[i].fullSum;
    }else if(STree[i].lazy==-1){
        STree[i].lazy = 0;
        for (int j = 0; j < 20; j++)
        {
            STree[i].pot[j] = 0;
        }STree[i].size = 0;
        STree[i].sum = 0;
    }
}
void push(int i){
    if(i > STsize) return;
    applay(i);
    
    
}void pull(int i){
    if(i > STsize) return;
    STree[i].size = STree[2*i].size+STree[2*i+1].size;
    STree[i].sum = STree[2*i].sum+STree[2*i+1].sum;
    for (int j = 0; j < 20; j++)
    {
        STree[i].pot[j] = STree[2*i].pot[j]+STree[2*i+1].pot[j];
        STree[i].sum += (1<<j)*((STree[2*i].size-STree[2*i].pot[j])*STree[2*i+1].pot[j]+(STree[2*i+1].size-STree[2*i+1].pot[j])*STree[2*i].pot[j]);
    }
}
void update(int i,int l,int r,int type){
    if((STree[i].l >= r) || (STree[i].r <= l)) {return;}
    if((STree[i].l >= l) && (STree[i].r <= r)) {STree[i].lazy = 3-2*type;return;}
    push(i);
    update(2*i,l,r,type);
    update(2*i+1,l,r,type);
    applay(2*i);
    applay(2*i+1);
    pull(i);

}

void dfs(int i,vector<vector<pair<int,int>>> &G){
    for(auto j : G[i]){
        if(xorSum[j.first]==-1){
            xorSum[j.first] = xorSum[i] ^ j.second;
            dfs(j.first,G);
        }
    }
}

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) {
    xorSum.resize(N,-1);
    xorSum[0] = 0;
    vector<vector<pair<int,int>>> G(N);
    for (int i = 0; i < N-1; i++)
    {
        G[u[i]].push_back({v[i],h[i]});
        G[h[i]].push_back({u[i],h[i]});
    }dfs(0,G);
    for (int i = 0; i < 2*STsize; i++)
    {
        for (int j = 0; j < 20; j++)
        {
            STree[i].Allpot[j] = 0;
            STree[i].pot[j] = 0;
        }STree[i].lazy = 0;
        STree[i].sum = 0;
        STree[i].size = 0;
    }
    for (int i = STsize; i < 2*STsize; i++){
        STree[i].fullSize = 1;
        STree[i].l = i-STsize;
        STree[i].r = i-STsize+1;
    }

    for (int i = 0; i < N; i++){
        for (int j = 0; j < 20; j++)
        {
            STree[i+STsize].Allpot[j] = (xorSum[i]&(1<<(j)))>>j;
        }
    
    }
    for (int i = STsize-1; i > 0; i--)
    {
        STree[i].fullSum = STree[2*i].fullSum + STree[2*i+1].fullSum;
        for (int j = 0; j < 20; j++)
        {
            STree[i].Allpot[j] = STree[2*i].Allpot[j]+STree[2*i+1].Allpot[j];
            STree[i].fullSum += (1<<j)*((STree[2*i].fullSize-STree[2*i].Allpot[j])*STree[2*i+1].Allpot[j]+(STree[2*i+1].fullSize-STree[2*i+1].Allpot[j])*STree[2*i].Allpot[j]);

        }STree[i].fullSize = STree[2*i].fullSize *2;
        STree[i].l = STree[2*i].l;
        STree[i].r = STree[2*i+1].r;
    }
    

    vector<ll> ans;
    for (int i = 0; i < Q; i++)
    {
        update(1,l[i],r[i]+1,t[i]);
        ans.push_back(STree[1].sum);
    }
    
    return ans;
}


