#P5105. 霸王龙和笨笨龙
-
ID: 3980
传统题
1000ms
128MiB
尝试: 10
已通过: 2
难度: 10
上传者:
霸王龙和笨笨龙
Description
霸王龙和笨笨龙是一对好朋友，他们两个都住在一个树形结构的树上，数上有n个节点，每个节点编号为1~n。节点a是霸王龙的住所，节点b是霸王龙公司所在地，节点c是笨笨龙的住所，节点d是笨笨龙公司所在地。每天霸王龙和笨笨龙都会在自己的住所和自己的公司所在地直接来回往返。请问有没有可能在某个节点，霸王龙和笨笨龙能够相遇？Input Format
第一行输入两个整数n和q，分别代表这棵树节点的个数和询问的个数。接下来n-1行，每行两个正整数u和v，表示节点u到节点v之间有一条边。
接下来q行，每行四个整数a,b,c,d表示节点的编号，也就是一次询问，意义如题所示。
对于100%的数据：1<=n,q<=1e5。
Output Format
输出q行，对于每一个询问，如果有可能在某个节点，霸王龙和笨笨龙能够相遇，输出"Y"，否则输出"N"。5 5
2 5
4 2
1 3
1 4
5 1 5 1
2 2 1 4
4 1 3 4
3 1 1 5
3 5 1 4Y
N
Y
Y
Y