CVBB ACM Team

此处介绍点分治算法的细节问题，此处不考虑 $w$。首先将整棵树的点分树建出来，对于一个数 $x$ 的操作将其记录在点分树的父亲们上，具体操作如下：

• 枚举 $x$ 的父亲们，包括 $x$ 自己。
• 如果枚举的 $i$ 的父亲存在，在父亲节点记录 $dis(fa_i,x)$ ，之后每个点跳到此结点的时候要减去这个值。如果点 $y$ 与 $x$ 恰好在 $fa_i$的两侧，则点 $y$ 的值的变化应为 $dis(fa_i,y)+dis(fa_i,x)$ ，前一个值可以通过记录每一个 $fa_i$ 被访问的次数进行操作，后一个值则正好在 $y$ 跳到此节点的时候通过 $fa_i$ 减掉了。
• 现在只需要防止 $y$ 与 $fa_{fa_i}$ 产生贡献，显然在跳 $fa_i$ 处记录 $dis(fa_{fa_i},x)$ 的值即可，在 $y$ 访问到 $fa_i$ 时即可提前将下一次的操作中和掉。注意此处的 $fa_i$ 包括 $x$ 自己，因为 $x$ 对于 $x$ 的子树是没有贡献的。