2020-2021:teams:farmer_john:2sozx:牛客多校第七场c
差别
这里会显示出您选择的修订版和当前版本之间的差别。
|
2020-2021:teams:farmer_john:2sozx:牛客多校第七场c [2020/08/07 16:25] 2sozx 创建 |
2020-2021:teams:farmer_john:2sozx:牛客多校第七场c [2020/08/07 16:41] (当前版本) 2sozx |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| =====A National Pandemic===== | =====A National Pandemic===== | ||
| + | 此处介绍点分治算法的细节问题，此处不考虑 $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$ 的子树是没有贡献的。 | ||
2020-2021/teams/farmer_john/2sozx/牛客多校第七场c.1596788748.txt.gz · 最后更改: 2020/08/07 16:25 由 2sozx
