P2664 树上颜色统计点分治虚树树上差分树上莫队

分类: IT文章 • 2022-07-14 09:27:35

树上差分O(n)的做法

　　考虑每种颜色对每个点的贡献,如果对于每种颜色我们把当前颜色的点删除,那么原来的树就会分成几个子树,对于一个点,当前颜色在和他同子树的点的点对路径上是不会出现的.考虑到有多种颜色,最后一个点的答案即为n * 颜色数 - 每种颜色节点时所在小树的size

P2664 树上颜色统计 点分治 虚树 树上差分 树上莫队