P3398 仓鼠找 sugar

Description

求树上 $a\sim b$与$c\sim d$ 两条路径有无交点。

Solution

手玩样例自造数据可以发现：
在树上：两条路径有交点当且仅当存在LCA在另一路径上——树的路径唯一特性保证性质

1.求LCA很简单，问题转化为判断点（LCA）在路径上
2.如何在路径上？
根据树上唯一简单路径：路径上的点$p$到路径端点$a,b$距离之和 等于 端点$a,b$距离。
简记为：$S_{p,a}+S_{p,b}==S_{a,b}$

我们根据点在路径上判断即可。

核心代码

		ll a=read(), b=read(), c=read(), d=read();
		ll lab=LCA(a, b), lcd=LCA(c, d);
		
		ll t1=LCA(lab, c), t2=LCA(lab, d), d1=LCA(lcd, a), d2=LCA(lcd, b);
		ll s1=dep[a]+dep[b]-2*dep[lab], s2=dep[c]+dep[d]-2*dep[lcd];
		//下方判断式已经过简化，可由“点在路径上”得出
		if(dep[lab]-dep[t1]-dep[t2]+dep[lcd]==0) cout<<"Y\n";//lab在c~d路径上
		else if(dep[lcd]-dep[d1]-dep[d2]+dep[lab]==0) cout<<"Y\n";//lcd在a~b路径上
		else cout<<"N\n";