icontofig | 发布于 2020-03-04 13:04:20 | 阅读量 514 | 点分治 线段树
发布于 2020-03-04 13:04:20 | 点分治 线段树
CodeForces 1303G. Sum of Prefix Sums 点分治+李超线段树
题目大意定义一种叫做前缀数组和的东西sum_i为某个数组的前缀和数组的前i项之和。 现在给定一个树,树上每个节点有权值,树上一条有向路径的权值定义为从起点u到终点v上的所有数字组成的前缀数组和。 求问这种路径权值的最大值是多少。 题解此题解为搬运CodeForces官方题解,为其中文翻译版本。(严正声明,可能中间会加一些个人的理解,代码的话个人的代码感觉还不如官方的好看所以就放官方的题解代码了) 首先确认这是一个树上路径问题,针对树上路径问题,一般可用的方法就是树分治和树链剖分。 考虑到这道题的路径权值的定义,我们并不能用树链剖分的传统的LCA和线段树的方法来进行计算,我们大概需要用搜索算法才
继续阅读
icontofig | 发布于 2020-02-03 23:19:32 | 阅读量 372 | 点分治 树状数组
发布于 2020-02-03 23:19:32 | 点分治 树状数组
luogu P4178 Tree 点分治+树状数组
题解树上点对距离问题,非常经典的点分治问题。 点分治的基本思路: 对于当前的树(子树),求出其重心,统计过重心的合法路径数,然后以重心为分隔点,分别递归对删除该重心后的子树进行求解(继续求重心、统计,再进行递归)。 重心的概念:若一个点为树的重心,那么其作为根的时候,其子树的大小的最大值最小。 重心的性质:重心分割出的子树的大小不会超过now_n/2,可以用来证明其时间复杂度为O(logn * 统计的时间)。 此题要求距离小于等于k的路径数目,如果把每一种都算出来累加复杂度是相当高的。 可以使用树状数组,不过要注意树状数组的0号位对答案是不会造成任何影响的,所以在统计入树状数组的时候要稍微处理
继续阅读