#97. [WJYOI DIF0.5][T4] 终点 · 再会

内存限制:256 MiB 时间限制:500 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: wangjunyi2013

题目描述

秋发现了一张族谱,它是一个类似树的结构:

  • 对于一个点 ,它会有一个父亲

  • 每一个点后面,都有一个字符 ,表示身份( 代表龙族, 代表人族)

现在给你 次查询,每次给你 个人,输出他们是否有最近龙族公共祖先(LCA,即Least Common Ancestors)

注:自己不能是自己的祖先!!

图1

如图,设结点 为龙族,那么 的最近龙族公共祖先为 ,深度

输入格式

第一行,两个正整数 ,表示树的结点数以及查询的次数

接下来 行,每行一个正整数 ,表示第 个结点种族是

接下来 行,每行包含两个正整数

接下来 行,每行一个正整数 ,以及 个正整数,表示要查询的人的结点编号

输出格式

个正整数,表示查询的答案,如果有输出 1 ,如果没有,输出 No Least Common Ancestors of the Dragon

样例

样例 #1

输入样例 #1

5 1
D R D R R
1 2
1 3
2 4
2 5
3 2 3 5

输出样例 #1

1

数据范围与提示

数据范围:

对于 的数据,保证 并且

本题由于骗分分值过高,开启捆绑测试!

时间限制

本题的时限开到

其他

图2

tw:我虽然承认你把这题包装的像一道新题,但这掩盖不了这就是一道模板题的现实,好水,甚至用不到倍增...