2021/8/17随笔

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

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

上一篇:C/S系统实现两数求和(非阻塞+epoll+心跳包检测用户在线状况+滚动日志+配置文件.)


下一篇:【转】 基于TFTP协议的远程升级设计