点分治

浅谈树分治算法

一句话讲,把分治做到树上。

树分治首先要把无根树转成有根树(如果是无根树,当然有根树就直接分治),即找一个点Root作为根。

如何找根?

为了分治的时效,我们需要分治的层数越少越好,于是想让找到的根下最大子树[……]

[点分治]POJ1741 Tree

题目大意

给一颗n个节点的树,每条边上有一个距离v。定义d(u,v)uv的最小距离。给定k值,求有多少点对(u,v)使uv的距离小于等于k

题解

如果用暴力枚举,那么时间复杂度为O(N^3)
用DFS,时间复杂度为O(N^2)
暴力不可取。
那么我们重[……]