一个动态加点的树可以实现的东西

xzggzh1 · 2021-02-15 10:31:56 · 个人记录

这里的动态加点指的是每次都加入一个点作为已知节点的儿子。

1. 可以利用倍增的方法，动态维护倍增数组求 \rm LCA，将新加入的点的 dep 设为负数，即可求得两点距离。

2. 动态求直径（CF690C3 ），利用直径的性质：所有直径的端点可以分为最多两个集合，且分别取这两个集合中的任意一元素，都可以构成直径。（可以先取出所有直径的交路径，其路径左/右的端点分别作为一个集合）。

3. 直径相关（CF842E ）：求有多少端点可以作为直径。（原理同上）。

4. 动态求重心：可以用 lct 动态维护子树 size ，然后发现加一个点最多使得重心往加点的方向动一步，然后模拟即可。