lct

[neal2018]

https://paste.ubuntu.com/p/N4nGms8Pwv/ https://www.luogu.com.cn/problem/P3690 1-based

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

struct LinkCutTree {
  struct TreeNode {
    int p = 0, s[2] = {0, 0}, rev = 0;
  };
  vector<TreeNode> tr;
  vector<int> stk;
  const function<void(int, int, int)> merge;
  LinkCutTree(int n, function<void(int, int, int)> &&op) : tr(n + 1), stk(n + 1), merge(op) {}
  void pull(int x) { merge(x, tr[x].s[0], tr[x].s[1]); }
  void rev(int x) { swap(tr[x].s[0], tr[x].s[1]), tr[x].rev ^= 1; }
  void push(int x) {
    if (tr[x].rev) rev(tr[x].s[0]), rev(tr[x].s[1]), tr[x].rev = 0;
  }
  bool is_root(int u) { return tr[tr[u].p].s[0] != u and tr[tr[u].p].s[1] != u; }
  void rotate(int x) {
    int y = tr[x].p, z = tr[y].p, k = tr[y].s[1] == x;
    if (!is_root(y)) tr[z].s[tr[z].s[1] == y] = x;
    tr[x].p = z, tr[y].s[k] = tr[x].s[!k];
    tr[tr[x].s[!k]].p = y, tr[x].s[!k] = y, tr[y].p = x;
    pull(y), pull(x);
  }

  void splay(int x) {
    int sz = 0, t = x;
    stk[++sz] = t;
    while (!is_root(t)) stk[++sz] = t = tr[t].p;
    while (sz) push(stk[sz--]);
    while (!is_root(x)) {
      int y = tr[x].p, z = tr[y].p;
      if (!is_root(y)) ((tr[z].s[1] == y) != (tr[y].s[1] == x)) ? rotate(x) : rotate(y);
      rotate(x);
    }
  }
  void access(int x) {
    for (int y = 0, t = x; t; y = t, t = tr[t].p) splay(t), tr[t].s[1] = y, pull(t);
    splay(x);
  }
  void make_root(int x) { access(x), rev(x); }
  int find_root(int x) {
    for (access(x); tr[x].s[0]; x = tr[x].s[0]) push(x);
    return splay(x), x;
  }
  void split(int x, int y) { make_root(y), access(x); }
  void link(int x, int y) {
    make_root(x);
    if (find_root(y) != x) tr[x].p = y;
  }
  void cut(int x, int y) {
    make_root(x);
    if (find_root(y) == x && tr[x].s[1] == y && !tr[y].s[0]) {
      tr[y].p = tr[x].s[1] = 0, pull(x);
    }
  }
  void set(int x, function<void(void)> &&modify) { splay(x), modify(), pull(x); }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, m;
  cin >> n >> m;

  vector<int> v(n + 1), s(n + 1);
  LinkCutTree t(n, [&](int u, int x, int y) { s[u] = s[x] ^ s[y] ^ v[u]; });
  for (int i = 1; i <= n; i++) cin >> v[i];

  while (m--) {
    int op, x, y;
    cin >> op >> x >> y;
    if (op == 0) {
      t.split(x, y);
      cout << s[x] << "\n";
    } else if (op == 1) {
      t.link(x, y);
    } else if (op == 2) {
      t.cut(x, y);
    } else {
      t.set(x, [&] { v[x] = y; });
    }
  }
}

[neal2018]

modified from jiangly's version

struct Node {
  Node *ch[2], *p;
  int id;
  bool is_rev;
  Node(int _id) : ch{nullptr, nullptr}, p(nullptr), id(_id), is_rev(false) {}
  friend void rev(Node *p) {
    if (p != nullptr) swap(p->ch[0], p->ch[1]), p->is_rev ^= 1;
  }
  void push() {
    if (is_rev) rev(ch[0]), rev(ch[1]), is_rev = false;
  }
  void pull() {}
  bool is_root() { return p == nullptr || (p->ch[0] != this && p->ch[1] != this); }
  bool pos() { return p->ch[1] == this; }
  void rotate() {
    Node *q = p;
    bool x = !pos();
    q->ch[!x] = ch[x];
    if (ch[x] != nullptr) ch[x]->p = q;
    p = q->p;
    if (!q->is_root()) q->p->ch[q->pos()] = this;
    ch[x] = q, q->p = this;
    pull(), q->pull();
  }
  void splay() {
    vector<Node *> s;
    for (Node *i = this; !i->is_root(); i = i->p) s.push_back(i->p);
    while (!s.empty()) s.back()->push(), s.pop_back();
    push();
    while (!is_root()) {
      if (!p->is_root()) {
        if (pos() == p->pos()) {
          p->rotate();
        } else {
          rotate();
        }
      }
      rotate();
    }
    pull();
  }
  void access() {
    for (Node *i = this, *q = nullptr; i != nullptr; q = i, i = i->p) {
      i->splay(), i->ch[1] = q, i->pull();
    }
    splay();
  }
  void make_root() { access(), rev(this); }
};
void link(Node *x, Node *y) { x->make_root(), x->p = y; }
void split(Node *x, Node *y) { x->make_root(), y->access(); }
void cut(Node *x, Node *y) { split(x, y), x->p = y->ch[0] = nullptr, y->pull(); }
bool connected(Node *p, Node *q) {
  p->access(), q->access();
  return p->p != nullptr;
}

[neal2018]

subtree info https://codeforces.com/contest/1681/submission/159995139

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;

struct LinkCutTree {
  struct TreeNode {
    int p = 0, s[2] = {0, 0}, rev = 0, sz = 1, v_sz = 0;
  };
  vector<TreeNode> t;
  vector<int> stk;
  LinkCutTree(int n) : t(n + 1), stk(n + 1) { t[0].sz = 0; }
  void merge(int u, int x, int y) { t[u].sz = t[x].sz + t[y].sz + t[u].v_sz + 1; }
  void pull(int x) { merge(x, t[x].s[0], t[x].s[1]); }
  void rev(int x) { swap(t[x].s[0], t[x].s[1]), t[x].rev ^= 1; }
  void push(int x) {
    if (t[x].rev) rev(t[x].s[0]), rev(t[x].s[1]), t[x].rev = 0;
  }
  bool is_root(int u) { return t[t[u].p].s[0] != u and t[t[u].p].s[1] != u; }
  void rotate(int x) {
    int y = t[x].p, z = t[y].p, k = t[y].s[1] == x;
    if (!is_root(y)) t[z].s[t[z].s[1] == y] = x;
    t[x].p = z, t[y].s[k] = t[x].s[!k];
    t[t[x].s[!k]].p = y, t[x].s[!k] = y, t[y].p = x;
    pull(y), pull(x);
  }
  void splay(int x) {
    int sz = 0, a = x;
    for (stk[++sz] = a; !is_root(a);) stk[++sz] = a = t[a].p;
    while (sz) push(stk[sz--]);
    while (!is_root(x)) {
      int y = t[x].p, z = t[y].p;
      if (!is_root(y)) ((t[z].s[1] == y) != (t[y].s[1] == x)) ? rotate(x) : rotate(y);
      rotate(x);
    }
  }
  void access(int x) {
    for (int y = 0, z = x; z; y = z, z = t[z].p) {
      splay(z), t[z].v_sz += t[t[z].s[1]].sz - t[y].sz, t[z].s[1] = y, pull(z);
    }
    splay(x);
  }
  void make_root(int x) { access(x), rev(x); }
  int find_root(int x) {
    for (access(x); t[x].s[0]; x = t[x].s[0]) push(x);
    return splay(x), x;
  }
  void split(int x, int y) { make_root(y), access(x); }
  void link(int x, int y) {
    make_root(y), make_root(x);
    if (find_root(y) != x) t[x].p = y, t[y].v_sz += t[x].sz, pull(y), pull(x);
  }
  void cut(int x, int y) {
    make_root(x);
    if (find_root(y) == x && t[x].s[1] == y && !t[y].s[0]) {
      t[y].p = t[x].s[1] = 0, pull(x);
    }
  }
  void set(int x, function<void(void)> &&modify) { splay(x), modify(), pull(x); }
};

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cout << fixed << setprecision(20);
  int n;
  cin >> n;
  LinkCutTree lct(n);
  vector<vector<pair<int, int>>> edges(n);
  for (int i = 0, u, v, c; i < n - 1; i++) {
    // cin >> u >> v >> c, u--, v--, c--;
    cin >> u >> v >> c, c--;
    edges[c].push_back({u, v});
    lct.link(u, v);
  }

  for (int i = 1; i <= n; i++) lct.make_root(i);
  ll res = 0;
  for (int c = 0; c < n; c++) {
    for (auto &[u, v] : edges[c]) lct.cut(u, v);
    for (auto &[u, v] : edges[c]) {
      lct.make_root(u), lct.make_root(v);
      res += ll(lct.t[u].sz) * lct.t[v].sz;
    }
    for (auto &[u, v] : edges[c]) lct.link(u, v);
  }
  cout << res << "\n";
}

[askdfjlas]

neal