有些问题
查看原帖
有些问题
920320
bianshiyang楼主2025/1/27 16:45

对于第一篇题解的暴力部分,首先是复杂度的问题,为什么三层循环加上一遍 dfs 是 O(n3)O(n^3) 的复杂度啊,我没有想到一个很好的解释复杂度均摊的问题。我的想法是假设直径上包含 xx 个点,那么复杂度应该是 x3(nx)x^3(n-x),求导可知极大值(此时也是最大值)在 x=3n4x=\frac{3n}{4} 取得,所以说 n=300n=300 时,最大应该是 2253×75=854296875225^3\times 75=854296875不该跑这么快啊

第二个问题是如果路径 FF 确定,偏心距应该是先求出树网中每个点 vvFF 中每个点 uu 的距离最小值,然后再把这些结果取个 max\max。代码里面实现的方法是先遍历每个 uu,然后求出树网中除了路径 FF 以外到 uu 距离最大的点 vv,这就是偏心距,这步转化有点没弄懂,有没有大佬可以解释一下。

2025/1/27 16:45
加载中...