BZOJ 4771 七彩树


题目链接: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 维护即可。

 

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ 4771 七彩树


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: , , , , ,