在 线 评 测 系 统
Toggle navigation
ZZULIOJ
常见问答
讨论版
题目列表
来源/分类
状态
排名
竞赛
考试&作业
Login
问题2525--咕咕的搜索序列
2525: 咕咕的搜索序列
时间限制:
1
Sec
内存限制:
128 MB
提交:
577
解决:
84
[
状态
] [
讨论版
] [
提交
] [命题人:
]
题目描述
咕咕已经学到树上的深度优先搜索 (dfs) 啦!由于同一棵树不同的 dfs 访问结点的次序不一样,咕咕干脆定义 了一个搜索序列:一开始序列为空,而每次离开这个点,并且不会再返回这个点时,就把这个点加入序列中, 最后返回到根节点后也把根节点加入这个序列中,这样就定义了一个与 dfs 一一对应的搜索序列!而且这个 搜索序列,也是所有点的一个排列。
对于一棵有根树(结点标号 1 到 n,以 1 为根),咕咕对它跑了一遍 dfs 得到了搜索序列后,它准备把这个序 列抄在纸上拿给咸鱼看。但是,粗心的咕咕在抄这个序列的时候,一些点被它忽略了,纸上的序列只有 m 个 点。待咸鱼看到纸上这个序列后,咸鱼就很好奇:咕咕那么粗心,只是抄少了点这么简单吗,会不会同时把 一些点的位置也给变化了呢?
现在,聪明的你,你能判断出来咕咕在抄的时候有没有把点的位置变化了吗?也就是说,咕咕给的 m 个点的 序列,真的能够由一个 dfs 得到的搜索序列删除几个点后得到吗?
输入
第一行一个整数 T(1≤ T ≤10
6
),表示有 T 组数据。
对于每组数据:
第一行有两个正整数 n 和 m(1≤m≤n≤10
6
),表示树的点数和咕咕给的序列的点数。
第二行有 n−1 个正整数 a
1
,a
2
,··· ,a
n−1
(1≤ a
i
≤i),表示点 a
i
是点 (i+1) 的父结点。
第三行有 m 个互不相同的正整数,b
1
,b
2
,··· ,b
m
(1≤b
i
≤n),表示咕咕给的序列。
输入保证同一个测试点下的所有数据的 n 的和不超过 10
6
。
输出
对每一组数据,输出一行。如果一定不能得到,输出 BAD GUGU ;否则输出 NOT BAD 。
样例输入
Copy
2 4 4 1 1 2 3 4 2 1 4 2 1 1 2 2 4
样例输出
Copy
NOT BAD BAD GUGU
提示
对于样例中给定的树,只存在两个不同的所搜序列:(3,4,2,1) 和 (4,2,3,1)。故对于序列 (2,4) 是没有办法 由任意一个搜索序列只通过删除点得到的。
来源/分类
CCPC2019河南省赛