树上连通块信息维护-尧图网络科技

黑白树

维护一棵树，他有 \(N\) 个节点，然后每个节点可能有两种颜色，黑色或白色。

你需要支持五种操作：

1.翻转 \(x\) 点的颜色。
2.把 \(x\) 点的同色连通块的点权加上 \(v\)。
3.查询 \(x\) 同色连通块的点权最大值。
4.将一条 \(x\) 到 \(y\) 的链的点的点权加上 \(v\)。
5.将一个子树内的点的点权加上 \(v\)。
对于全部数据 \(n\le2\times10^5\)，保证答案不超过 int。

假如没有操作 4，5，我们可以用 LCT 直接维护同色连通块信息。

对于这个问题有一种精妙的重链剖分加线段树的做法。（很反直觉，但是我目前还没找出问题，在这里先描述做法，还没有实现）

先考虑刻画一个同色连通块，首先我们定根，然后让连通块中深度最小的点作为其代表元，记其为 \(u\)，颜色为 \(c\)，那么在同一联通块的点 \(v\) 满足 \(v\) 在 \(u\) 的子树中且 \(u\) 到根路径上颜色不为 \(c\) 的点数量与 \(v\) 到根路径上颜色不为 \(c\) 的数量相等。

然后考虑怎么快速找一个点所在极大同色联通块的代表元，简单二分/倍增就能做到 2log，通过一些优化、精细实现可以 1log，不太必要。

我们维护 dfn 序的线段树，对于线段树的一个节点，其对应区间 \([L,R]\)，取这个区间的 lca 为 \(u\)，我们维护 \(cnt_{0/1}\) 为 \(u\) 到根路径上颜色为 \(0/1\) 的点个数，维护 \(mx_{0/1},tag_{0/1}\) 维护与 \(u\) 联通的最大值，以及对两种颜色连通块加的懒标记。

对于操作 2，我们先找到代表元 \(u\)，然后对于 \(u\) 子树的 dfn 区间 \([l,r]\) 在线段树上对应的 log 个节点打上对应颜色的标记。

这里有可能节点的 dfn 区间属于 \([l,r]\) 但节点不在 \(u\) 的连通块里，我们在打标记和下放标记时，对于颜色 \(c\) 要判断两个点的 \(cnt_{1-c}\) 是否相等才下放。

然后是操作 1，发现修改点 \(u\) 相当于对子树的 \(cnt_c\) 减 \(1\)，\(cnt_{1-c}\) 加 \(1\)，这个可以直接用线段树区间修改打懒标记维护，然后修改时还影响了 \(u\) 的信息，要把 \(u\) 在线段树上所在的叶子的 \(mx_{0/1}\) 的信息交换，然后更新叶子到根的信息。

对于操作 3，我们同样找到代表元 \(u\)，并找到子树的 dfn 区间在线段树上的节点，答案就是这些节点中 \(cnt_{1-c}\) 跟 \(u\) 相等的 \(mx_c\) 的最大值。

至于操作 4，5 与前边的操作在线段树上不冲突，直接拍成 dfn 上的区间修改打懒标记就行，是简单的。

于是我们就在 \(n\log ^2n\) 的复杂度解决了这个问题~~常数巨大~~。