【SDOI2017】树点涂色

Source and Judge

SDOI2017
Loj2001

Record

3h

Analysis

请先思考后再展开

感觉很有趣的一道题
关键性质:每种颜色的性质一定是向上的一条链

显然以dfs序为下标,维护每个点到根节点路径上的权值
显然x到y的权值为 $d(x)+d(y)-d(LCA)+1$
(这个随便讨论一下lca是否有孩子和自己相同颜色)

关键是第一个操作,合并颜色块的总次数应该只有n
( $\sum num[color]$ ,因为总有一点点被侵占的地方,这里并不严谨,个人这个感觉)
我自己的想法死在了并查集我不会断开操作
看到这个断开, 以我的知识面只会想到lct
将每种颜色的所有点放到相同splay中,修改操作和access非常类似
然后每次合并的贡献,就是当前子树所有种类都-1,不过如果某孩子颜色和x相同,需要+1
因为我们始终维护好splay,所以如果存在,那个孩子就是splay中x的右孩子

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/31df.html
转载请注明出处,谢谢!