传送门
题目描述
小仓鼠的和他的基(mei)友(zi)sugar住在地下洞穴中,每个节点的编号为1~n。地下洞穴是一个树形结构。这一天小仓鼠打算从从他的卧室(a)到餐厅(b),而他的基友同时要从他的卧室(c)到图书馆(d)。他们都会走最短路径。现在小仓鼠希望知道,有没有可能在某个地方,可以碰到他的基友?
小仓鼠那么弱,还要天天被zzq大爷虐,请你快来救救他吧!
输入
第一行两个正整数n和q,表示这棵树节点的个数和询问的个数。
接下来n-1行,每行两个正整数u和v,表示节点u到节点v之间有一条边。接下来q行,每行四个正整数a、b、c和d,表示节点编号,也就是一次询问,其意义如上。
输出
对于每个询问,如果有公共点,输出大写字母“Y”;否则输出“N”。
样例
Input
5 52 54 21 31 45 1 5 12 2 1 44 1 3 43 1 1 53 5 1 4Output
YNYYY
题解
- 如果两个仓鼠走的路有交集的话,那么其中一个的LCA一定在另一个路径上。
- 设a,b的LCA为x,c,d的LCA为y,如果
depth[x] > depth[y]
,x必然在cy或者dy上,即x必然和c、d其中一个点有公共祖先,并且这个点的在x下面;同理,如果depth[x] < depth[y]
,y必然和a、b其中一个有公共祖先,并且这个点在y下面。
Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 | #include |