对于第一篇题解的暴力部分,首先是复杂度的问题,为什么三层循环加上一遍 dfs 是 O(n3) 的复杂度啊,我没有想到一个很好的解释复杂度均摊的问题。我的想法是假设直径上包含 x 个点,那么复杂度应该是 x3(n−x),求导可知极大值(此时也是最大值)在 x=43n 取得,所以说 n=300 时,最大应该是 2253×75=854296875,不该跑这么快啊。
第二个问题是如果路径 F 确定,偏心距应该是先求出树网中每个点 v 到 F 中每个点 u 的距离最小值,然后再把这些结果取个 max。代码里面实现的方法是先遍历每个 u,然后求出树网中除了路径 F 以外到 u 距离最大的点 v,这就是偏心距,这步转化有点没弄懂,有没有大佬可以解释一下。