Link Cut Tree

LCT 动态树问题

Posted by TH911 on February 16, 2026

Luogu P3690 动态树(LCT)

给定 $n$ 个点、每个点的权值和 $m$ 次操作:

  • 0 x y 代表询问从 $x$ 到 $y$ 的路径上的点的权值的 $\operatorname{xor}$ 和。保证 $x$ 到 $y$ 是联通的。
  • 1 x y 代表连接 $x$ 到 $y$,若 $x$ 到 $y$ 已经联通则无需连接。
  • 2 x y 代表删除边 $(x,y)$,不保证边 $(x,y)$ 存在。
  • 3 x y 代表将点 $x$ 上的权值变成 $y$。

$1\leq n\leq 10^5,1\leq m\leq3\times10^5$。

咕。