BZOJ4771 七彩树

题意

多次询问树上$x_i$的子树中深度在$dep[x]\sim dep[x+d_i]$的不同的颜色种数,强制在线

题解

考虑离线并且每次查询的深度是最大深度,对于每一种颜色按照dfs序排序,把每个点的贡献先看成1,但由于同一个子树中的相同颜色会被重复计算,那么在相邻点的LCA处减去一,这样颜色数就是子树的权值和。

如果要考虑深度,那么可以离线以后按照点的深度排序,维护一个set,每次插入一个点,把这个点相邻的LCA处减一,把之前的加上。这里用线段树维护dfs序上的权,按照深度离线后查询子树和即可满足二维的约束。

如果强制再线,那么可以把上面的线段树可持久化,用主席树维护即可。

NOTICE

主席树插入的时候要从前一个根传递答案(包含左右子树),每次插入都要新开一个点。

代码

Leave a Reply

Your email address will not be published. Required fields are marked *