#include "happy.h"

using namespace std;

const int MAXN = 300000;
const int MAXBIT = 20;

vector<pair<int, int>> g[MAXN];
int xr[MAXN];

struct SegmentTree {
  struct Node {
    int actual[MAXBIT][2], orig[MAXBIT][2], lazy;
  } tree[4 * MAXN], aux;
  int n;

  Node join(Node a, Node b) {
    for(int i = 0; i < MAXBIT; i++) {
      aux.actual[i][0] = a.actual[i][0] + b.actual[i][0];
      aux.actual[i][1] = a.actual[i][1] + b.actual[i][1];
      aux.orig[i][0] = a.orig[i][0] + b.orig[i][0];
      aux.orig[i][1] = a.orig[i][1] + b.orig[i][1];
    }
    return aux;
  }

  void build(int node, int left, int right) {
    if(left == right) {
      for(int i = 0; i < MAXBIT; i++) {
        tree[node].orig[i][(xr[left] >> i) & 1]++;
      }
    } else {
      int middle = (left + right) / 2;
      build(2 * node, left, middle);
      build(2 * node + 1, middle + 1, right);
      tree[node] = join(tree[2 * node], tree[2 * node + 1]);
    }
  }

  void init(int n) {
    this->n = n;
    build(1, 0, n - 1);
  }

  void addLazy(int node, int type) {
    for(int i = 0; i < MAXBIT; i++) {
      for(int bit = 0; bit < 2; bit++) {
        tree[node].actual[i][bit] = tree[node].orig[i][bit] * (2 - type);
      }
    }
    tree[node].lazy = type;
  }

  void propagate(int node) {
    if(tree[node].lazy > 0) {
      addLazy(2 * node, tree[node].lazy);
      addLazy(2 * node + 1, tree[node].lazy);
      tree[node].lazy = 0;
    }
  }

  void update(int node, int left, int right, int qleft, int qright, int type) {
    if(qleft <= left && right <= qright) {
      addLazy(node, type);
    } else {
      propagate(node);
      int middle = (left + right) / 2;
      if(qleft <= middle) {
        update(2 * node, left, middle, qleft, qright, type);
      }
      if(middle < qright) {
        update(2 * node + 1, middle + 1, right, qleft, qright, type);
      }
      tree[node] = join(tree[2 * node], tree[2 * node + 1]);
    }
  }

  void update(int st, int dr, int type) {
    update(1, 0, n - 1, st, dr, type);
  }

  Node query() {
    return tree[1];
  }
} aint;

void dfs(int node, int parent) {
  for(auto edge : g[node]) {
    if(edge.first != parent) {
      xr[edge.first] = xr[node] ^ edge.second;
      dfs(edge.first, node);
    }
  }
}

vector<long long> 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++) {
    g[u[i]].push_back({v[i], h[i]});
    g[v[i]].push_back({u[i], h[i]});
  }
  dfs(0, -1);

  aint.init(n);
  vector<long long> answers;
  for(int i = 0; i < q; i++) {
    aint.update(l[i], r[i], t[i]);
    SegmentTree::Node answer = aint.query();
    long long sum = 0;
    for(int j = 0; j < MAXBIT; j++) {
      sum += (1LL << j) * answer.actual[j][0] * answer.actual[j][1];
    }
    answers.push_back(sum);
  }
  return answers;
}
