关于思路的一处问题
查看原帖
关于思路的一处问题
549521
boy♂Next♂dooor楼主2024/7/24 11:09

很多题解都是这么说的:“那么在直径上取路径的话有两种情况,一种是直径的端点离这个路径最远,还有一种情况是非直径的点离这条路径最远。” 然后再取max。

但是这个非直径的点不应该是在那个尺取的树网的核上吗,为什么可以直接预处理所有的点的不经过直径的偏心距呢?

不应该是遍历核(ui,uj)得到每一个的偏心距

max(max⁡i<=k<=jd[uk],dis(u1,ui),dis(uj,ut)),d[uk]是uk不经过直径的偏心距,dis指路径长,u1,ut为直径端点max(\max_{i<=k<=j}d[u_k],dis(u1,u_i),dis(uj,u_t)),d[u_k]是u_k不经过直径的偏心距,dis指路径长,u1,ut为直径端点

吗? 为什么可以直接根据《算进》上所说的根据什么直径的最长性变成

max(max⁡1<=k<=td[uk],dis(u1,ui),dis(uj,ut)),d[uk]是uk不经过直径的偏心距,dis指路径长max(\max_{1<=k<=t}d[u_k],dis(u1,u_i),dis(uj,u_t)),d[u_k]是u_k不经过直径的偏心距,dis指路径长

? 而且据我所知的直径最长性,任意d[uk]d[u_k]作为直径的分支,应该小于分支点到端点的距离,即d[uk]<dis(u1,uk)<dis(u1,ui)和dis(uj,ut)d[u_k]<dis(u1,u_k)<dis(u1,u_i)和dis(uj,u_t),那岂不是不用考虑这种情况了?

2024/7/24 11:09
加载中...