
样例如图,假设其中标黑点是我求出的直径。
设 6 号点为直径左端点,3 号点为直径右端点。那么按照题解一的思路,求出的必经节点链的两个端点为 3 和 4,满足样例输出。
可是我一直在想一个问题,6 号节点也满足题解中的这句话:
因为还有可能出现这种情况,即dis[k]=ls[k],这样就变成了k的左边的所有边都不可能是必经边。
之所以 6 号点可以满足这个条件,是因为 6 号点没有向非直径节点连接的边,且 6 号点为直径的左端点,所以 dis[k]=0,ls[k]=0, 所以满足条件。
但是显然,6 号点不能作为我们求出的端点。
所以,为什么 6 号点不能作为我们求出的端点(即使我们知道让它作为端点是错误的)?