很多题解都是这么说的:“那么在直径上取路径的话有两种情况,一种是直径的端点离这个路径最远,还有一种情况是非直径的点离这条路径最远。”
然后再取max。
但是这个非直径的点不应该是在那个尺取的树网的核上吗,为什么可以直接预处理所有的点的不经过直径的偏心距呢?
不应该是遍历核(ui,uj)得到每一个的偏心距
max(i<=k<=jmaxd[uk],dis(u1,ui),dis(uj,ut)),d[uk]是uk不经过直径的偏心距,dis指路径长,u1,ut为直径端点
吗?
为什么可以直接根据《算进》上所说的根据什么直径的最长性变成
max(1<=k<=tmaxd[uk],dis(u1,ui),dis(uj,ut)),d[uk]是uk不经过直径的偏心距,dis指路径长
?
而且据我所知的直径最长性,任意d[uk]作为直径的分支,应该小于分支点到端点的距离,即d[uk]<dis(u1,uk)<dis(u1,ui)和dis(uj,ut),那岂不是不用考虑这种情况了?