P2056 [ZJOI2007] 捉迷藏 题解 / 点分树（点分治）学习笔记

· · 题解

:::::info[闲话] 你说得对，这道题线段树能做，但是我还是花了一天时间复习了点分治并学习了点分树。
::::: :::::info[题目基本信息] 考察：点分树（省选/NOI-）。
题目简介：
给定一棵有 n 个点的树，每个点初始时都是白色，现在有 q 次操作，操作类型有 2 种：

  1. 修改一个点的颜色为白色或黑色。
  2. 求树上白点两两间最远的距离。

数据范围：

时间限制：4s 到 5s。
空间限制：250MB。
::::: 点分树经典题，对点分树进行详解。
:::::success[点分树详解] 众所周知，许多树上暴力过不了的原因是树的高度可能较高从而得到错误的时间复杂度，而点分树就很好的解决了这一点。
点分树是这样建立的：

  1. 找到这棵树的重心。
  2. 以这棵树的重心为根，将这棵树划分为若干以重心的儿子为根的子树。
  3. 将这棵树的重心与子树的重心连边。
  4. 递归所有子树。

由于重心的性质，每个子树的大小至少减半，所以最多有 \log_2 n 层，这时有一些暴力就变得可行。
但是由于点分树和原树的形态大相径庭，所以适用范围较小。
::::: 在这个题中，我们先建出点分树，然后维护三个数据结构：

这些在点分树维护的同时就能维护出来，对于修改操作直接从该点往上暴力跳维护即可。
虽然确实细节比较多。
:::::warning[坑点] 用 multiset 维护 a_u,b_u,ans 会被卡常，需要使用可删堆。
::::: 时间复杂度为 \Theta((n+q)\log^2n)，空间复杂度为 \Theta(n\log n)。

code