如何求两条链的交

Benzenesir / 2023-08-29 / 原文

  1. 如果两条链的 lca 相同,则意味着错开求的 lca 中,另外两个就是端点
  2. 反之,链的交则是一条祖先链,不难发现错位 lca 中不为原端点的点就是新端点