秋发现了一张族谱,它是一个类似树的结构:
对于一个点 ,它会有一个父亲
每一个点后面,都有一个字符 ,表示身份( 代表龙族, 代表人族)
现在给你 次查询,每次给你 个人,输出他们是否有最近龙族公共祖先(LCA,即Least Common Ancestors)
如图,设结点 为龙族,那么 ,, 的最近龙族公共祖先为 ,深度
第一行,两个正整数 ,表示树的结点数以及查询的次数
接下来 行,每行一个正整数 ,表示第 个结点种族是
接下来 行,每行包含两个正整数
接下来 行,每行一个正整数 ,以及 个正整数,表示要查询的人的结点编号
个正整数,表示查询的答案,如果有输出 1 ,如果没有,输出 No Least Common Ancestors of the Dragon
1
No Least Common Ancestors of the Dragon
5 1 D R D R R 1 2 1 3 2 4 2 5 3 2 3 5
对于 的数据,保证 并且
本题由于骗分分值过高,开启捆绑测试!
本题的时限开到 的 倍
tw:我虽然承认你把这题包装的像一道新题,但这掩盖不了这就是一道模板题的现实,好水,甚至用不到倍增...