#include #include #include #include #include #include using ll = long long; using namespace std; #define rep(i, n) for (int i = 0, _rep_ub = (n); i < _rep_ub; i++) #define fastio \ cin.tie(0); \ ios::sync_with_stdio(0); // BEGIN: [structure/lct/link-cut-tree-subtree] // https://ei1333.github.io/library/structure/lct/link-cut-tree-subtree.hpp template struct LinkCutTreeSubtree { struct Node { Node *l, *r, *p; KEY key; SUM sum; bool rev; int sz; bool is_root() const { return !p || (p->l != this && p->r != this); } Node(const KEY &key, const SUM &sum) : l(nullptr), r(nullptr), p(nullptr), key(key), sum(sum), rev(false), sz(1) {} }; const SUM ident; LinkCutTreeSubtree(const SUM &ident) : ident(ident) {} Node *make_node(const KEY &key) { auto ret = new Node(key, ident); update(ret); return ret; } Node *set_key(Node *t, const KEY &key) { expose(t); t->key = key; update(t); return t; } void toggle(Node *t) { swap(t->l, t->r); t->sum.toggle(); t->rev ^= true; } void push(Node *t) { if (t->rev) { if (t->l) toggle(t->l); if (t->r) toggle(t->r); t->rev = false; } } void update(Node *t) { t->sz = 1; if (t->l) t->sz += t->l->sz; if (t->r) t->sz += t->r->sz; t->sum.merge(t->key, t->l ? t->l->sum : ident, t->r ? t->r->sum : ident); } void rotr(Node *t) { auto *x = t->p, *y = x->p; if ((x->l = t->r)) t->r->p = x; t->r = x, x->p = t; update(x), update(t); if ((t->p = y)) { if (y->l == x) y->l = t; if (y->r == x) y->r = t; update(y); } } void rotl(Node *t) { auto *x = t->p, *y = x->p; if ((x->r = t->l)) t->l->p = x; t->l = x, x->p = t; update(x), update(t); if ((t->p = y)) { if (y->l == x) y->l = t; if (y->r == x) y->r = t; update(y); } } void splay(Node *t) { push(t); while (!t->is_root()) { auto *q = t->p; if (q->is_root()) { push(q), push(t); if (q->l == t) rotr(t); else rotl(t); } else { auto *r = q->p; push(r), push(q), push(t); if (r->l == q) { if (q->l == t) rotr(q), rotr(t); else rotl(t), rotr(t); } else { if (q->r == t) rotl(q), rotl(t); else rotr(t), rotl(t); } } } } Node *expose(Node *t) { Node *rp = nullptr; for (auto *cur = t; cur; cur = cur->p) { splay(cur); if (cur->r) cur->sum.add(cur->r->sum); cur->r = rp; if (cur->r) cur->sum.erase(cur->r->sum); update(cur); rp = cur; } splay(t); return rp; } void link(Node *child, Node *parent) { expose(child); expose(parent); child->p = parent; parent->r = child; update(parent); } Node *cut(Node *child) { expose(child); auto *parent = child->l; child->l = nullptr; parent->p = nullptr; update(child); return parent; } void evert(Node *t) { expose(t); toggle(t); push(t); } Node *lca(Node *u, Node *v) { if (get_root(u) != get_root(v)) return nullptr; expose(u); return expose(v); } Node *get_kth(Node *x, int k) { expose(x); while (x) { push(x); if (x->r && x->r->sz > k) { x = x->r; } else { if (x->r) k -= x->r->sz; if (k == 0) return x; k -= 1; x = x->l; } } return nullptr; } Node *get_root(Node *x) { expose(x); while (x->l) { push(x); x = x->l; } return x; } SUM &query(Node *t) { expose(t); return t->sum; } }; // END: [structure/lct/link-cut-tree-subtree] // BEGIN: [tree/levelancestor] // (https://beet-aizu.github.io/library/tree/levelancestor.cpp) struct LevelAncestor { vector> G, par, lad; vector dep, nxt, len, pth, ord, hs; LevelAncestor(int n) : G(n), dep(n), nxt(n, -1), len(n), pth(n), ord(n), hs(n + 1, 0) { int h = 1; while ((1 << h) <= n) h++; par.assign(h, vector(n, -1)); for (int i = 2; i <= n; i++) hs[i] = hs[i >> 1] + 1; } void add_edge(int u, int v) { G[u].emplace_back(v); G[v].emplace_back(u); } void dfs(int v, int p, int d, int f) { if (nxt[v] < 0) { par[0][nxt[v] = v] = p; len[v] = dep[v] = d; for (int u : G[v]) { if (u == p) continue; dfs(u, v, d + 1, 0); if (len[v] < len[u]) nxt[v] = u, len[v] = len[u]; } } if (!f) return; pth[v] = lad.size(); lad.emplace_back(); for (int k = v;; k = nxt[k]) { lad.back().emplace_back(k); pth[k] = pth[v]; if (k == nxt[k]) break; } for (;; p = v, v = nxt[v]) { for (int u : G[v]) if (u != p and u != nxt[v]) dfs(u, v, d + 1, 1); if (v == nxt[v]) break; } } void build(int r = 0) { int n = G.size(); dfs(r, -1, 0, 1); for (int k = 0; k + 1 < (int)par.size(); k++) { for (int v = 0; v < n; v++) { if (par[k][v] < 0) par[k + 1][v] = -1; else par[k + 1][v] = par[k][par[k][v]]; } } for (int i = 0; i < (int)lad.size(); i++) { int v = lad[i][0], p = par[0][v]; if (~p) { int k = pth[p], l = min(ord[p] + 1, (int)lad[i].size()); lad[i].resize(l + lad[i].size()); for (int j = 0, m = lad[i].size(); j + l < m; j++) lad[i][m - (j + 1)] = lad[i][m - (j + l + 1)]; for (int j = 0; j < l; j++) lad[i][j] = lad[k][ord[p] - l + j + 1]; } for (int j = 0; j < (int)lad[i].size(); j++) if (pth[lad[i][j]] == i) ord[lad[i][j]] = j; } } int lca(int u, int v) { int h = par.size(); if (dep[u] > dep[v]) swap(u, v); for (int k = 0; k < h; k++) if ((dep[v] - dep[u]) >> k & 1) v = par[k][v]; if (u == v) return u; for (int k = h - 1; k >= 0; k--) { if (par[k][u] == par[k][v]) continue; u = par[k][u]; v = par[k][v]; } return par[0][u]; } int distance(int u, int v) { return dep[u] + dep[v] - dep[lca(u, v)] * 2; } int up(int v, int d) { if (d == 0) return v; v = par[hs[d]][v]; d -= 1 << hs[d]; return lad[pth[v]][ord[v] - d]; } // from u to v int next(int u, int v) { if (dep[u] >= dep[v]) return par[0][u]; int l = up(v, dep[v] - dep[u] - 1); return par[0][l] == u ? l : par[0][u]; } }; // END: [tree/levelancestor] struct LcaSum { ll psum, csum, cnt, weight; ll lsum, lcnt, lcnt2; LcaSum() : psum(0), csum(0), cnt(0), weight(0), lsum(0), lcnt(0), lcnt2(0) {} void toggle() { swap(psum, csum); } void merge(pair cost, const LcaSum &parent, const LcaSum &child) { auto [c, id] = cost; cnt = parent.cnt + child.cnt + (c > 0) + lcnt; weight = parent.weight + child.weight + id * lcnt + c; ll pcnt = parent.cnt + lcnt; ll pcnt2 = parent.cnt * parent.cnt + lcnt2; psum = parent.psum + child.psum + lsum; ll ccnt = child.cnt + lcnt; ll ccnt2 = child.cnt * child.cnt + lcnt2; csum = parent.csum + child.csum + lsum; psum += c * pcnt + id * (pcnt * pcnt - pcnt2) / 2; csum += c * ccnt + id * (ccnt * ccnt - ccnt2) / 2; csum += parent.weight * (ccnt + (c > 0)); psum += child.weight * (pcnt + (c > 0)); } void add(const LcaSum &chsum) { lsum += chsum.csum; lcnt += chsum.cnt; lcnt2 += chsum.cnt * chsum.cnt; } void erase(const LcaSum &chsum) { lsum -= chsum.csum; lcnt -= chsum.cnt; lcnt2 -= chsum.cnt * chsum.cnt; } } e; const int MAX = 50050; using LCT = LinkCutTreeSubtree>; LCT::Node *vs[MAX] = {}; int main() { fastio; int n, q; cin >> n >> q; LCT lct(e); LevelAncestor la(n + 1); rep(i, n + 1) vs[i] = lct.make_node({0, i}); la.add_edge(0, 1); rep(_i, n - 1) { int a, b; cin >> a >> b; lct.evert(vs[b]); lct.link(vs[b], vs[a]); la.add_edge(a, b); } la.build(); rep(_i, q) { int u, r, v; cin >> u >> r >> v; lct.set_key(vs[u], {u - vs[u]->key.first, u}); lct.evert(vs[r]); ll p = v != r ? la.next(v, r) : 0; if (p) { lct.evert(vs[p]); lct.cut(vs[v]); } LcaSum res = lct.query(vs[v]); cout << res.csum << '\n'; if (p) { lct.evert(vs[v]); lct.link(vs[v], vs[p]); } } return 0; }