高度由习惯堆积

标签 点分治 下的文章

February 9, 2019

HDU4871 Shortest-path tree(点分治)

题目题面大意是给你一个图,要你构建出一棵最短路树,再询问经过k个点的最长路径长度以及最长路径条数。思路点分治。点分治的思路是这样的:对于一个点$x$而言,对答案有影响的路径要么经过点$x$要么不经过,利用这点进行分治。点分治首先要找出一个重心。重心是指以该点为根所有的子树中sz最大的最小。然后,对于每一棵子树进行处理,统计答案(点分治题目不同的地方就在这,其它都是板子)之后再递归进重心的子树...