树上路径求交

对于路径 \((u,v)\) 和 \((s,t)\)

  • 判断是否有交:
    • 对于两点 \(\operatorname{LCA}\) 的深度较大者,判断它是否在另一条路径上
  • 求交出来的路径
    • \(\operatorname{LCA}(u,s),\operatorname{LCA}(u,t),\operatorname{LCA}(v,s),\operatorname{LCA}(v,t)\) 四者中,深度较大的两个即为交出的路径的两端点
    • 此方法前提是已经判断了交不为空
上一篇:2020CCPC河南省赛 发通知(离散+差分)


下一篇:最近公共祖先(LCA)笔记