• 周二. 8月 16th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

2021/8/17随笔

admin

11月 28, 2021

询问树上a到b,c到d的两条路径是否相交
如果相交,记 x=lca(a,b),y=lca(c,d),则必有x在c~d路径上或y在a~b路径上
若交点是树上最高的交点,并且不是lca,说明这条链向上还有在链上的父节点,两链都不是lca,并且是树上最高的交点,说明,这交点上连接着两条不同的父节点,树不可能有两个父节点,所以不可能有交点是树上最高的交点,并且不是lca.

即树上两链交点集合中必至少有一个lca。

发表回复

您的电子邮箱地址不会被公开。