AC. 梦想

frank_c1

[BZOJ 1468] Tree

发布于2016年02月28日 | 暂无评论 | 530阅读 | 树分治

题目描述

给你一棵树,以及这棵树上边的距离.问有多少对点它们两者间的距离小于等于K。

输入格式

N(n<=40000) 接下来n-1行边描述管道,按照题目中写的输入,接下来是K。

输出格式

共一行,有多少对点之间的距离小于等于K。

题目解析

很经典的一道题目,算是树分治的入门题吧。

我们考虑一棵有根树,有一对点,这两个点间的路径要么穿过根,要么是在根的某棵子树内部。于是就可以得到这样一棵朴素的算法:以当前结点为根,计算来自它的不同子树中的点对有多少对的路径是合法的(也包括子树中某点到根这样的点对),然后递归下去。这个算法看起来不错,但是有致命的缺陷。出题人只需构造一个链的数据就可以卡掉这个算法。也即,这个算法最坏情况复杂度可能达到O(n ^ 2)

怎样让树尽可能平衡一些呢?如果我们每次选取树的重心,计算出经过重心的答案,然后把树分为若干子树,再选取子树的重心…… 如此递归下去,就可以保证递归层数是O(\log {n})的,总复杂度就可以保证在O(n \log {n})。这就是树的点分治的应用,在此膜一膜漆子超神犇的论文课件