TheTree
作者:杨景钦
关键词:枚举
题目简述
已知有一棵有根树, 以及深度为的点有个, 求在所有可能的树中, 直径最长的树的直径是多少
令为最大的深度, , 保证存在至少一棵可能的树。
算法一
设直径的一端深度为, 另一端为, 与的最近公共祖先深度为
不妨设
直接枚举, 如何判断是否合法呢? 显然 且 对于
于是直接暴力枚举, 判断是否合法即可, 复杂度
算法二
考虑优化算法一, 注意到, 令一定最优(因为保证存在一棵树) 于是可以少枚举
假设 为0
再观察可以发现。 如果已经枚举了, 那么一定是
我们从大往小枚举, 顺便维护就可以了。
复杂度