题解：P11330 [NOISG 2022 Finals] Grapevine

lzyqwq · 2024-11-27 18:46:42 · 题解

这种简单题没能一遍胡对，是不是该退役了。

P11330 [NOISG 2022 Finals] Grapevine

• 给出 n 个点的树，初始所有点都是白色，有 3 种操作共 q 次：
  • 1 u：求所有黑点到 u 的距离的最小值。
  • 2 u：反转点 u 的颜色。
  • 3 u v w：将连接 u,v 的边权值改为 w。

考虑两点树上距离 \text{dis}(u,v)=\text{dep}_u+\text{dep}_v-2\text{dep}_{\text{LCA}(u,v)}。那么首先暴力地考虑枚举 \text{LCA}(u,v)。

当 \text{LCA}(u,v)=u 时，只需要选取子树内深度最小的点即可。

否则，考虑 u 根链 1\rightsquigarrow \text{fa}_u 上的一个点 p 作为 \text{LCA}(u,v)，则 v 必须在 p 子树内且不在 p 在 1\rightsquigarrow u 路径上的子节点 \text{son}_p 的子树中。此时只需要求这个区域内 \text{dep}_v-2\text{dep}_p 的最小值。

考虑重剖，则 1\rightsquigarrow u 上只有 \mathcal{O}(\log n) 条轻边。则对于路径上这些边没有覆盖的点 p，\text{son}_p 都是 p 的重儿子。记 f_p 表示在 p 子树中且不在 p 重儿子子树中的黑点 v 的 \text{dep}_v-2\text{dep}_p 的最小值。那么对于根链上的每一条重链，她有一部分贡献就是除去底端的一段前缀，在 \text{dfn} 序上也是一段区间。

对于重链底端的点，只有 \mathcal{O}(\log n) 个，并且一定是一条重链顶端的父亲 \text{fa}。那么对于每一条重链，计算在她顶端的父亲子树中且不在她顶端子树中的区域内的黑点 v 的 \text{dep}_v 的最小值。贡献就是 \text{dep}_u+\text{dep}_v-2\text{dep}_{\text{fa}}。

至此，跳链时的所有查询都能被表示成 \mathcal{O}(1) 个 \text{dfn} 上的区间的并。由于有修改还要区间查询，考虑线段树维护。

由于仅查询黑点的信息，因此维护的时候，对于黑点就维护她的 \text{dep}，对于白点维护她的深度加上 \inf。记处理过后的深度为 D，和真实深度 \text{dep} 区分。那么 f_p 就变成对应区域内 D_v-2\text{dep}_p 的最小值。

对于 2 u 操作，相当于对 D_u 加或减 \inf。还要考虑哪些 f_p 会发生变化，显然 p 满足：

那么 p 只能是 1\rightsquigarrow u 上轻边连接的深度较小的结点。这样的 p 只有 \mathcal{O}(\log n) 个，直接暴力跳链然后重新计算即可。

对于 3 u v w 操作，不妨记 u 为较深的结点。假设这条边权值增加了 k。考虑她对 D,\text{dep},f 分别有什么影响：

• - **口胡时没考虑到的地方**：对于 $u$ 子树内的点 $p$，其子树内黑点 $v$ 和 $p$ 的 $\text{dep}$ 都要 **加 $k$**。结合式子发现每个点的新贡献都变成原来的贡献减 $k$，那么肯定仍然选择先前选的点，对应的子树内的所有 $f_p$ 减 $k$，转化成 $\text{dfn}$ 序后是区间加。 - 对于 $1\rightsquigarrow \text{fa}_u$ 上的点，和上面只有 $\mathcal{O}(\log n)$ 个点的 $f$ 会用到 $u$ 子树内的黑点，对于这些点暴力重新计算即可。 - 对于剩下的点，其子树内部一点不存在 $u$ 子树内的点，不用考虑。

那么基本做完了。最后整理一下，因为实现和思路有一些小出入：

• 用线段树维护 D,f。维护 f 理论上比 D 多一个单点修改，但我不想写两个线段树，所以在代码中先查询一遍原来的值，然后加上增量。
• 由于重新计算 f 和求答案的时候需要用到单点 \text{dep}_u，而修改是 3 u v w 操作的区间加，因此用树状数组维护。
• 用 map 存每一时刻的边权。用一个数组记录每个点的颜色。

AC Link / Code