P10776 Jabby's shadows 题解

· · 题解

题意

维护一棵树，有非负边权，每个点初始为黑色，需要支持：

## 题解 讲一个通用 Top Tree 做法，可以单 log 做此题同时可以支持 Link、Cut 等操作。 考虑 SATT，假设没有路径染色操作，我们大致需要维护以下信息： - 这个点的颜色：`nco`； - 这条边的权值：`val`； - 两个端点的颜色：`col[0/1]`； - 簇路径长度：`len`； - 簇路径上点的颜色是否全部相同：`peq`； - 两个界点到其所在白/黑色连通块内最远点距离：`dis[0/1][0/1]`； - 两个界点所在白/黑色连通块的直径：`ans[0/1][0/1]`； 如果有路径染色操作，我们还需要维护以下信息： - 簇路径被全部染成白/黑色后的 dis：`cds[0/1][0/1][0/1]`； - 簇路径被全部染成白/黑色后的 ans：`cas[0/1][0/1][0/1]`； - 染色标记：`tag`； 那么路径染色时直接将 `ans` 和 `dis` 赋值为对应的 `cas` 和 `cds` 即可。 因为 Pushdown 很简单，接下来我们考虑如何 Pushup。 为了方便进行细节讨论，我们再明确一下一些词的定义： > 对于同时维护点和边的 SATT，以上界点为例，若当前簇内深度最小的是一条边，那么上界点实际定义为与这条边相连的深度更小的点，是在簇外的；否则定义为簇内深度最小的点。 > > 而对于端点，以上端点为例，它被定义为簇内深度最小的点。 > > 那么就可以区分“端点”和“界点”：端点一定是在簇内的，界点不一定是在簇内。比如对于一条边的基簇，它没有端点，并且两个界点都在簇外。 那么可以看出，无论是 Compress 还是 Rake，这些信息都是可以快速合并的，以 `dis` 和 `ans` 为例： - 在 Rake 时: - 上界点的 dis 可以来自两个簇的 dis； - 下界点的 dis 可以来自原 dis 或跨过上界点延伸到另一个簇中； - 上界点的 ans 可以来自两个簇的 ans，还可以跨过界点； - 下界点的 ans 可以来自原 ans 或者跨过上界点延伸到另一个簇中，或者另一个簇的 ans； - 在 Compress 时： - 上界点的 dis 可以来自上面的簇的 dis 或者延伸到下面的簇； - 上界点的 ans 可以来自上面的簇的 ans 或者当上面的簇路径颜色相同时，下面的簇的 ans 或跨过界点。 其实没什么细节，最主要就是维护的信息比较多而已…… ## 代码 完整代码见 [link](https://www.cnblogs.com/laijinyi/p/18728202#jabbys-shadows)。 ## 闲话 这题我写了三天 我也不知道我为什么要学这么没用的科技。