这个帖子里的树剖被卡常了，但是这只是因为他的写法不够优美。

亲测树剖可过，只需加上以下几种优化：

• 所有函数加上 inline。
• 将线段树的 $l, r$ 放进函数内传参，$sum$ 和 $tag$ 用数组，不要用结构体，下面是反面教材：

struct node {
  int l, r;
  int sum, tag;
} t[N << 2];

• 不要用 vector，用链式前向星。
• 可以在枚举路径时循环展开，比如：

int ans = 0;
while (q--) {
  ans = 0;
  int a, b, c; read(a, b, c);
  update(a, b, 1);
  ans = max(ans, query(a, c));
  ans = max(ans, query(b, c));
  update(a, b, -1);
  update(a, c, 1);
  ans = max(ans, query(b, c));
  update(a, c, -1);
  cout << ans << '\n';
}

• 使用快读，最好用 fread 版的。
• 将线段树中的 lson(x) 和 rson(x) 用 x << 1 和 x << 1 | 1 替换。
• 加边的时候只加父亲到儿子的边。

然后就可以轻松愉快地用树剖草过此题了！