Description

?

维护一棵树，每次需要执行以下两个操作：

1. 新增一个叶子节点
2. 查询新增的叶子节点与原树上的多少个点满足两点的距离小于等于两点点权相加之和。

强制在线。

Solution

前置芝士

1. 高速平衡树（指除了\(Fhq-Treap\)和\(Splay\)以外的平衡树，或者你有高超的卡常技能也行）
2. 动态点分治（替罪羊树式点分树）

前言

由于这道题涉及到的东西比较繁琐，所以接下来将分块讲解。

动态点分治

首先，如果这道题不强制在线的话要怎么做，我们观察一下题目给出的关于条件的式子：
\[ dis_{i,j}\le r_i+r_j \]
考虑重心\(u\)，那么式子就变成了
\[ dis_{i,u}+dis_{j,u}\le r_i + r_j \]
移项
\[ dis_{i,u}-r_i\le r_j - dis_{j,u} \]
所以如果不强制在线，应该就得到了一个比较显然的做法：建立点分树，对于每个点维护一棵平衡树，存储\(r_i-dis_{i,u}\)，对于一个新加入的点\(x\)，就在点分树上暴力跳祖先，并进行查询和更新。

然而，本题要求强制在线（说的就是你，毒瘤的强制在线！）。

平衡树

因为本题中所用到的平衡树功能比较单一，所以可以写高速平衡树。

博主查阅了部分博文，发现主要有以下几种平衡树：

1. 替罪羊树，重构因子为\(0.86\)时的时间复杂度比较优秀

2. \(Splay\)或\(Fhq-Treap\)，高超的卡常技巧

3. \(SBT\)

4. \(Treap\)

PS：当然，以上几种平衡树我并没有一一试验

替罪羊式点分树

前面说到离线的做法，既然强制在线，那我们就不能把点分树一次性全部建出来了。

那怎么办呢，每次加一个点就重构一次点分树不就行了。

考虑点分治时的分治中心，之所以要选在重心，是因为选在重心时效率最高，那么分治中心如果不在重心，显然也是可以的

[WC2014]紫荆花之恋 - 动态点分治 + 平衡树（Part 2）

原文：https://www.cnblogs.com/newbielyx/p/12130236.html