网站设计基础知识,重庆seo博客推广,搜狗网站优化软件,什么网站可以做图赚钱P2664 树上游戏
对于树上n个点#xff0c;每个点有不同颜色#xff0c;求解每个点到其他点的路径上不同颜色个数之和。
首先看到这种树上点对问题#xff0c;我们可以想到点分治#xff0c;然后考虑每次分治如何求解答案#xff0c;本质上就是一个数颜色的问题#xff…P2664 树上游戏
对于树上n个点每个点有不同颜色求解每个点到其他点的路径上不同颜色个数之和。
首先看到这种树上点对问题我们可以想到点分治然后考虑每次分治如何求解答案本质上就是一个数颜色的问题然后我们采用类似的思路考虑每个颜色第一次出现时的贡献但是现在的问题就在于一条链是没有前后的所以我们可能需要一些计算。
首先对于分治中心的贡献计算我们可以从中心开始dfs在每个颜色第一次出现的地方有size的贡献。
然后考虑每个子树内部的点对于在从当前点到分治中心的链上出现过的颜色我们直接将其统计为cnt(sizrt−sizx)cnt(siz_{rt}-siz_{x})cnt(sizrt−sizx)然后考虑没有在这一段出现的颜色那就是之前一开始在其他子树内部出现的贡献但是要减去在当前这条链上已经出现的颜色贡献和当前所在子树内部的颜色贡献。
这个具体实现的确是很麻烦首先一步dfs求解出所有子树的贡献之和对应颜色的总贡献以及每个子树分别产生的贡献之和然后具体处理每个子树内的点时候先dfs这个子树求解该子树对应颜色的贡献然后再dfs一边该子树分别计算每个点的答案 ansitot−sumu−∑k∈Scol[k]cnt∗(sizrt−sizu)ans_itot-sum_u-\sum_{k\in{S}}col[k]cnt*(siz_rt-siz_u)ansitot−sumu−k∈S∑col[k]cnt∗(sizrt−sizu) 这就是最终的结果
其实整理一下发现我们应该这样思考首先数颜色问题都是考虑第一次或者最后一次出现的贡献那么现在问题需要求解每个点的答案我们就考虑每个点的链分为两类颜色一类第一次出现在当前子树他们的贡献可以直接计算一类出现在其他子树他们的贡献就是对应的子树大小之和所以我们想到这样统计
O(n)的fansy做法:
现在我们直接不考虑点分治直接考虑每种颜色的贡献可以发现去掉某种颜色后树会变成若干个连通块并且每个连通块仍然是一颗树然后对于每个连通块的贡献就是siz−sizusiz-siz_usiz−sizu那么对于每个点的答案就应该是cnt∗n−∑csizc,icnt*n-\sum_{c}siz_{c,i}cnt∗n−∑csizc,i然后我们考虑如何统计首先将每个颜色的贡献放在深度最小的点上这样子就是一个树上差分了只不过这里是子树覆盖那么我们只需要在dfs过程中维护dfs栈的每种颜色的对应信息即可。
