Vertex Flip Query 题解

思路

删去所有连接异色顶点的边后，第 $3$ 类操作询问的就是顶点所在连通块的权值和。难点在于一次翻色可能同时改变很多关联边，不能逐边维护动态连通性。

把原树固定根后，用 static top tree 将树的合并过程表示成深度为 $O(\log N)$ 的二叉表达树。点更新只会影响一个加入顶点节点及其到表达树根的祖先，因此可以在对数时间内重算。

做法

以下状态同时支持从父边界和子边界两个方向读取，从而在不更换固定根的前提下完成任意顶点换根询问。

簇状态

点簇只有一个边界。对两种可能的边界颜色分别维护能从该边界接入的侧向同色分量权值和。合并两个点簇时，两种颜色的槽分别相加。

路径簇有两个有序边界，维护首尾颜色、首尾所在同色块的权值和，以及首尾是否连通。合并相邻路径簇时，只有中间两个端点颜色相同才可能连通。若左簇首尾连通，右簇首块可加入新的首块；反向同理。新的首尾连通当且仅当两个子簇内部都连通且中间颜色相同。

每个路径簇同时保存两个观察方向的状态。把路径簇接到父边界时，只把靠近父边界的同色块放入对应颜色槽；加入一个顶点时，只读取与该顶点当前颜色相同的槽，再加上顶点权值。

操作处理

颜色翻转或权值增加后，自底向上重算对应表达节点的全部祖先。

询问顶点 $v$ 时，从 $v$ 的加入顶点节点沿表达树走到根。路径旁的兄弟簇互不相交，并与起始簇恰好覆盖整棵树。维护当前同色分量是否仍接触路径簇的两个边界；只有靠近当前分量的边界颜色等于 $C_v$ 时，才加入该边界块，并依据连通标记决定能否继续穿过。经过侧向合并时收集父顶点的其他点簇，父顶点颜色仍为 $C_v$ 才接入这些贡献。

正确性证明

点簇的两个槽只合并挂在同一边界的互不相交侧向簇，因此不会混入异色贡献，也不会重复计数。

路径簇的两个子簇之间只有一条连接边。按中间颜色是否相同以及两个子簇的首尾连通性更新首尾块，完整覆盖了跨越与断开两种情况，所以路径状态由归纳始终正确。

询问上升路径的每个兄弟簇都不含当前查询簇，且这些兄弟簇与起始簇构成整棵树的一个不交分解。双向状态保证每次都从靠近 $v$ 的边界读取贡献。因此被加入的顶点恰好是能从 $v$ 沿全同色路径到达的顶点，所得权值和就是答案。

复杂度

构造表达树需要 $O(N\log N)$ 次常数状态合并并占用 $O(N)$ 空间。每次操作访问表达树的一条祖先路径，时间复杂度为 $O(\log N)$。