[Luogu]P3703 [SDOI2017] 树点涂色题解
本文最后更新于 52 天前,其中的信息可能已经有所发展或是发生改变。

题解

一种思路自然的染色解法。

对全树进行轻重链剖分,维护一棵线段树,分别记录每个点的颜色、每个点到根的颜色种数。

需要支持:单点查询颜色、区间修改颜色、区间修改颜色种数、区间查询颜色种数最大值。

对于每一种颜色,记录当前状态:深度最浅的点 $st(col)$、深度最深的点 $ed(col)$,每次插入新颜色时,$st(col) = 1$,$ed(col) = x$,用于辅助更新颜色种数的变化。


对于操作二,记 $f(i)$ 为每个点到根的颜色数,这个是线段树维护了的,可以考虑用树上差分类似的做法?但其实这里有个细节,就是颜色种数的合并问题。

可以发现,$\operatorname{lca}(x,y)$ 的颜色,至多与 $x,y$ 中的一个相同。那么分类讨论一下:

如果 $\operatorname{lca}(x,y)$ 的颜色与 $x,y$ 都不同,那么可以 $f(x) + f(y) – 2\times f(\operatorname{lca}(x,y)) + 1$,即计算出两点到祖先下的路径中的颜色数,然后加上祖先的颜色。
如果 $\operatorname{lca}(x,y)$ 与 $x,y$ 中的一个相同,假定与 $x$ 相同,那么 $y$ 的贡献可以直接用 $f(y) – f(\operatorname{lca}(x,y))$ 计算,而 $x$ 的贡献用 $f(x) – f(\operatorname{lca}(x,y))$ 后,将本该计入的祖先处的颜色也减去了,因此还需要 $+1$,整体仍是 $f(x) + f(y) – 2\times f(\operatorname{lca}(x,y)) + 1$.

因此,对于操作二,可以直接输出 $f(x) + f(y) – 2\times f(\operatorname{lca}(x,y)) + 1$.


对于操作三,就是查询子树内 $f(i)$ 的最大值。

仅剩的问题,就是操作一会如何更新数据了。

操作一

可以暴力跳颜色段维护,具体地,对于 $1 \to x$ 的路径上的每段连续颜色,都用线段树更新其贡献。

对于这条路径上经过的颜色段,有两种可能:全段颜色都在路径上,或部分颜色在路径上。

全段颜色

AllInclude

对于这种情况,我们需要将该颜色的贡献消去。
可以发现,对于 $1 \to i$ 的路径,只要 $i \in \operatorname{subtree}(st(col))$,那么该颜色就会对 $f(i)$ 产生贡献。
相应地,我们可以对 $i \in \operatorname{subtree}(st(col))$ 的 $f(i)$ 做区间减法,具体地,区间减 $1$ 即可。

部分颜色

然而,还有一种情况:部分颜色在路径上。

PartInclude

此时我们仍然在 $\operatorname{subtree}(st(col))$ 中消去贡献,但是问题出现了:分叉出去的颜色段中,这个颜色依然是有贡献的。
因此我们还准备好了 $ed(col)$,利用这个 $ed(col)$ 一路向上跳,直到紧挨当前染色路径时,对其子树整体加一。

这个向上跳的操作可以利用轻重链剖分来做。$ed(col)$ 如果属于对应点的轻子树,那么一路跳上来最后会有 $x = y$,此时返回上一个重链的顶部即可。否则直接返回重儿子。详细见代码。
然后再令 $p \to st(col)$ 更新一下颜色段。


消去原本的颜色段的贡献后,再计入当前颜色的贡献,给整棵树加一即可。

代码

虽然代码很长,但大部分都是模板,还是比较好实现的。

本文标题:[Luogu]P3703 [SDOI2017] 树点涂色题解
本文作者:Clouder
本文链接: https://www.codein.icu/lp3703/
转载请标明。
暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇