icontofig | 发布于 2020-02-03 23:19:32 | 阅读量 344 | 点分治 树状数组
发布于 2020-02-03 23:19:32 | 点分治 树状数组
luogu P4178 Tree 点分治+树状数组
题解树上点对距离问题,非常经典的点分治问题。 点分治的基本思路: 对于当前的树(子树),求出其重心,统计过重心的合法路径数,然后以重心为分隔点,分别递归对删除该重心后的子树进行求解(继续求重心、统计,再进行递归)。 重心的概念:若一个点为树的重心,那么其作为根的时候,其子树的大小的最大值最小。 重心的性质:重心分割出的子树的大小不会超过now_n/2,可以用来证明其时间复杂度为O(logn * 统计的时间)。 此题要求距离小于等于k的路径数目,如果把每一种都算出来累加复杂度是相当高的。 可以使用树状数组,不过要注意树状数组的0号位对答案是不会造成任何影响的,所以在统计入树状数组的时候要稍微处理
继续阅读