P3398 仓鼠找sugar

判断树上两条路径是否相交

我们可以判断两条路径各自的LCA的子树是否有交集即可，或者可以判断其中一条路径的LCA 是否在另一条路径上

inline int LCA(int x, int y) {
	while(top[x]^top[y]) {
		if(dep[top[x]] < dep[top[y]]) std::swap(x, y);
		x = fa[top[x]];
	}
	return dep[x] < dep[y] ? x : y;
}

inline bool in(int anc, int b) {
	return dfn[anc] <= dfn[b] && dfn[b] <= dfn[anc] + siz[anc] - 1;
}

inline int dis(int a, int b) {
	return dep[a] + dep[b] - (dep[LCA(a, b)] << 1);
}

int main() {
	read(n);
	read(q);
	int x, y;
	rep(i, 2, n) {
		read(x);
		read(y);
		G.add(x, y);
		G.add(y, x);
	}
	dfs(1);
	dfs2(1, 1);

	int a, b, c, d;
	while(q--) {
		read(a);
		read(b);
		read(c);
		read(d);

		int x(LCA(a, b));
		int y(LCA(c, d));
		
		
		if(dis(a, y) + dis(b, y) == dis(a, b) || dis(c, x) + dis(d, x) == dis(c, d)) {
			puts("Y");
		} else
			puts("N");
		/*if( (in(x, c) || in(x, d)) && (in(y, a) || in(y, b))  ) {
			puts("Y");
		} else puts("N");*/
	}

	return 0;
}