树上路径的交

两条路径$u_1\to v_1,u_2\to v_2$的交这样计算：

• 首先计算出$x_1=lca(u_1,u_2),x_2=lca(v_1,v_2),x_3=lca(u_1,v_2),x_4=lca(v_1,u_2)$，然后取这四个点中深度最大的两个点$y_1,y_2$。
• 若$y_1=y_2$，且$y_1$的深度大于了$lca(u_1,v_1)$或者$lca(u_2,v_2)$的深度，那么交不存在；否则，交就是$y_1$到$y_2$之间的路径。

// Road中的t：t=0表示空集，t=-1表示全集，t=1表示u到v的路径
struct Road {
	int u,v,t;
	Road(int u=0,int v=0,int t=-1): u(u),v(v),t(t){};
};
bool cmp_dep(int x,int y) { return dep[x]>dep[y]; }
Road Inter(Road A,Road B) {
	if(A.t==0||B.t==0) return Road(0,0,0);
	if(A.t==-1) return B;
	if(B.t==-1) return A;
	int tmp[4]={LCA(A.v,B.v),LCA(A.u,B.u),LCA(A.v,B.u),LCA(A.u,B.v)};
	sort(tmp,tmp+4,cmp_dep);
	if(tmp[0]==tmp[1]&&(dep[tmp[0]]<dep[LCA(A.u,A.v)]||dep[tmp[0]]<dep[LCA(B.u,B.v)]))
		return Road(0,0,0);
	return Road(tmp[0],tmp[1],1);
}
bool Onchain(Road A,int x) {
	if(A.t==0) return 0;
	if(A.t==-1) return 1;
	if(A.t==-1) return 1;
	int tmp[2]={LCA(A.u,x),LCA(A.v,x)};
	if(dep[tmp[0]]<dep[tmp[1]]) swap(tmp[0],tmp[1]);
	if(tmp[0]==x&&tmp[1]==LCA(A.u,A.v)) return 1;
	return 0;
}