tree-intersect

假设两条链 \((a_1, b_1), (a_2, b_2)\) 的 LCA 分别为 \(c_1, c_2\)。再求出 \((a_1, a_2), (a_1, b_2), (b_1, a_2), (b_1, b_2)\) 的 LCA，记为 \(d_1, d_2, d_3, d_4\)。将 \((d_1, d_2, d_3, d_4)\) 按照深度从小到大排序，\((c_1,c_2)\) 也从小到大排序。两条链有交当且仅当 \(\mathrm{dep}[c_1] \leq \mathrm{dep}[d_1]\) 且 \(\mathrm{dep}[c_2] \leq \mathrm{dep}[d_3]\)，则 \((d_3, d_4)\) 是链交的两个端点。