分类:点分治

[期望+点分治+FFT]bzoj3451: Tyvj1953 Normal


<h3>题目描述</h3> 某天WJMZBMR学习了一个神奇的算法:树的点分治! 这个算法的核心是这样的: 消耗时间=0 Solve(树 a) 消耗时间 += a 的 大小 如果 a 中 只有 1 个点 退出[......]

浅谈树分治算法


一句话讲,把分治做到树上。 树分治首先要把无根树转成有根树(如果是无根树,当然有根树就直接分治),即找一个点$Root$作为根。 <h3>如何找根?</h3> 为了分治的时效,我们需要分治的层数越少越好,于是想让[......]

[点分治]POJ1741 Tree


<h3>题目大意</h3> 给一颗$n$个节点的树,每条边上有一个距离$v$。定义$d(u,v)$为$u$到$v$的最小距离。给定$k$值,求有多少点对$(u,v)$使$u$到$v$的距离小于等于$k$。 <h3>题解</h3>[......]