TheTree

作者：杨景钦

关键词：枚举

题目简述

已知有一棵有根树， 以及深度为$i$的点有$A_i$个， 求在所有可能的树中， 直径最长的树的直径是多少
令$n$为最大的深度， $n \leq 50$， 保证存在至少一棵可能的树。

算法一

设直径的一端深度为$a$， 另一端为$b$， $a$与$b$的最近公共祖先深度为$c$

不妨设$a \ge b \ge c$

直接枚举$a, b, c$, 如何判断是否合法呢？ 显然$A_c \ge 1$ 且$A_i \ge 2$ 对于$b \le i \le a$

于是直接暴力枚举， $O(N)$判断是否合法即可， 复杂度$O(N^4)$

算法二

考虑优化算法一， 注意到， 令$a = n$一定最优（因为保证存在一棵树） 于是可以少枚举$a$

假设$A_{n+1}$ 为0

再观察可以发现。 如果已经枚举了$c$， 那么$b$一定是$Min(i, n+1 \ge i \ge c 且 A_i \leq 1) - 1$

我们从大往小枚举$c$， 顺便维护$b$就可以了。

复杂度$O(N)$