Observing the Tree

#include <bits/stdc++.h>
using namespace std;

typedef int64_t i64;

const int SIZE = 2e5+5;

struct Info {
  int l, r;
  i64 a, b;
  Info (int l, int r, i64 a, i64 b) : l(l), r(r), a(a), b(b) {}
};


int64_t l[SIZE << 2], r[SIZE << 2], st[SIZE << 2], NODES = 0;

bool hasFlag[SIZE << 2];
vector<Info> flag[SIZE << 2];

int newLeaf(int value) {
  int p = ++NODES;
  l[p] = r[p] = 0;
  st[p] = value;
  return p;
}

int newParent(int lef, int rig) {
  int p = ++NODES;
  l[p] = lef;
  r[p] = rig;
  st[p] = st[lef] + st[rig];
  return p;
}

int newLazyKid(int node, int a, int b, int ul, int ur, int L, int R);

void propagate(int node, int L, int R) {
  if (hasFlag[node]) {
    if (L != R) {
      for (auto info : flag[node]) {
        int M = L+(R-L)/2;
        l[node] = newLazyKid(l[node], info.a, info.b, info.l, info.r, L, M);
        r[node] = newLazyKid(r[node], info.a, info.b, info.l, info.r, M + 1, R);
      }
      flag[node].clear();
    }
    hasFlag[node] = false;
  }
}

int newLazyKid(int node, int a, int b, int ul, int ur, int L, int R) {
  int p = ++NODES;
  l[p] = l[node];
  r[p] = r[node];
  flag[p] = flag[node];
  hasFlag[p] = true;

  flag[p].push_back(Info(ul, ur, a, b));

  int64_t left = L, right = R;
  int64_t A = a + (int64_t)b * (L - ul);

  st[p] = st[node] + (int64_t)A * (right - left + 1) + (int64_t)b * (right - left) * (right - left + 1) / 2;

  return p;
}

int build(int L, int R) {
  if (L == R) return newLeaf(0);
  int M = L+(R-L)/2;
  return newParent(build(L, M), build(M+1, R));
}

int update(int node, int L, int R, int ul, int ur, int64_t a, int64_t b) {
  if (ur < L or R < ul) return node;
  if (ul <= L and R <= ur) return newLazyKid(node, a, b, ul, ur, L, R);
  int M = L+(R-L)/2;
  propagate(node, L, R);
  return newParent(update(l[node], L, M, ul, ur, a, b),
                   update(r[node], M + 1, R, ul, ur, a, b));
}

int64_t query(int node, int L, int R, int a, int b) {
  if (b < L || R < a)   return 0;
  if (a <= L && R <= b) return st[node];
  int M = L+(R-L)/2;
  propagate(node, L, R);
  return query(l[node], L, M, a, b) +
         query(r[node], M + 1, R, a, b);
}

int n, m;
vector<vector<int>> gr;

int timer;
vector<int> h, pos, sz, dad;

void dfs(int u, int par = -1) {
  sz[u] = 1;
  for (int &to : gr[u]) if (to != par) {
    dad[to] = u;
    dfs(to, u);
    sz[u] += sz[to];
    if (sz[to] > sz[gr[u][0]] or gr[u][0] == par)
      swap(gr[u][0], to);
  }
}

void build_hld(int u, int par = -1) {
  pos[u] = ++timer;
  for (int to : gr[u]) if (to != par) {
    h[to] = (to == gr[u][0] ? h[u] : to);
    build_hld(to, u);
  }
}

int currentRoot = -1;

int64_t query_path(int a, int b) {
  if (pos[a] < pos[b]) swap(a, b);

  if (h[a] == h[b]) return query(currentRoot, 1, n, pos[b], pos[a]);

  return query(currentRoot, 1, n, pos[h[a]], pos[a]) + query_path(dad[h[a]], b);
}

void iterative_update_path(int a, int b, int64_t ai, int64_t r) {
  for(;;) {
    if (h[a] != h[b]) {
      // chain distintas
      if (pos[a] < pos[b]) {
        // sobe o b
        currentRoot = update(currentRoot, 1, n, pos[h[b]], pos[b], ai, r);
        b = dad[h[b]];
      } else if (pos[b] < pos[a]) {
        // sobe o a
        currentRoot = update(currentRoot, 1, n, pos[h[a]], pos[a], ai, r);
        a = dad[h[a]];
      }
    } else {
      // mesma chain
      if (pos[a] < pos[b]) {
        // sobe o b
        currentRoot = update(currentRoot, 1, n, pos[a], pos[b], ai, r);
        break;
      } else if (pos[b] < pos[a]) {
        // sobe o a
        currentRoot = update(currentRoot, 1, n, pos[b], pos[a], ai, r);
        break;
      }
    }
  }
}

int main() {
  cin.tie(0)->sync_with_stdio(0);

  cin >> n >> m;

  gr.assign(n, vector<int>());
  h.assign(n, 0);
  pos.assign(n, 0);
  sz.assign(n, 0);
  dad.assign(n, -1);

  for (int i = 0; i < n-1; ++i) {
    int a, b; cin >> a >> b, --a, --b;
    gr[a].push_back(b);
    gr[b].push_back(a);
  }

  dfs(0, -1);
  build_hld(0, -1);

  int firstRoot = build(1, n);
  currentRoot = firstRoot;

  vector<int> roots{ currentRoot };

  int64_t lastAns = 0;
  int cntChanges = 0;
  while (m--) {
    char op; cin >> op;

    if (op == 'c') {
      int64_t x, y, a, b;
      cin >> x >> y >> a >> b;
      x = (x + lastAns) % n + 1;
      y = (y + lastAns) % n + 1;

      --x; --y;

      ++cntChanges;
      iterative_update_path(x, y, a, b);

      roots.push_back(currentRoot);
    } else if (op == 'q') {
      int64_t x, y; cin >> x >> y;
      x = (x + lastAns) % n + 1;
      y = (y + lastAns) % n + 1;

      --x; --y;

      lastAns = query_path(x, y);

      cout << lastAns << '\n';
    } else if (op == 'l') {
      int64_t x; cin >> x;
      x = (x + lastAns) % (cntChanges + 1);
      currentRoot = roots[x];
    }
  }

}