BZOJ 4771 七彩树

发布于 2017-12-23  157 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=4771

题意:

一棵 n 个点的有根树,编号依次为 1 到 n,其中 1 号点是根节点。每个节点都被染上了某一种颜色,其中第 i 个节点的颜色为 c[i]。如果 c[i]=c[j],那么我们认为点 i 和点 j 拥有相同的颜色。定义 depth[i] 为 i 节点与根节点的距离,为了方便起见,你可以认为树上相邻的两个点之间的距离为 1。
询问 x 子树里且 depth 不超过 depth[x]+d 的所有点中出现了多少种本质不同的颜色。
 

这个子树内和距离不超过 d 的限制可以转移到二维平面上考虑,然后二维数据结构维护...?

显然维护不了,因为信息没法合并。

换一个套路,对层建主席树。

对于同色点对,在 lca 处丧失一个贡献,为了不重不漏只统计 dfs 序相邻的那些,这个对每组颜色开个 set 维护即可。

 


一个非常弱的准退役OIER