[Luogu5599]失昼城的守星使 | K-D Space

[EndSaH]

https://endsah.cf/blog/Luogu5599-%E5%A4%B1%E6%98%BC%E5%9F%8E%E7%9A%84%E5%AE%88%E6%98%9F%E4%BD%BF/#more

Description给定一棵 $n$ 个节点的树，边有边权，每个节点初始有一个颜色（黑 / 白）。有 $m$ 个操作： 1 x: 翻转 $x$ 节点的颜色。 2 x y: 询问所有黑色节点到 $x \to y$ 这条链上的距离之和。 （定义一个节点到链的距离为到链上节点距离的最小值） $$1 \le n, m \le 2 \times 10 ^5$$