[DS记录]Bzoj#4771. 七彩树

command_block · 2020-04-08 22:12:08 · 个人记录

比做这题更难的恐怕是找到这题。在哪里找就不说了,无论这个困难是否消失,也请不要回复相关内容。

• 题意 : 给出一棵n个点的树,每个点有一个颜色。

  每次给定u,d,询问点u的子树内深度不超过dep(u)+d的点集内,一共出现了多少种颜色。

  多组数据,强制在线,\sum n,\sum m\leq5\times 10^5.

子问题 : CF893F Subtree Minimum Query

先不考虑深度。

对于一种颜色,建立包括根的虚树并把虚树上的路径全部+1即可。

这里有一个技巧叫做虚树差分 : 把每个点的权值置为1,然后按dfs排序后,相邻两个点的LCA权值-1,树上前缀和即可。

可以认为在LCA处吧两条路径合并成一条,所以要减去某一条的贡献,由于按dfs序考虑正确性同虚树。

考虑加入深度限制,就是二维数点了。搞个主席树就做完了。