2525: 咕咕的搜索序列
时间限制: 1 Sec 内存限制: 128 MB
提交: 371 解决: 40
[提交] [状态] [讨论版] [命题人:外部导入]
题目描述
咕咕已经学到树上的深度优先搜索 (dfs) 啦！由于同一棵树不同的 dfs 访问结点的次序不一样，咕咕干脆定义 了一个搜索序列：一开始序列为空，而每次离开这个点，并且不会再返回这个点时，就把这个点加入序列中， 最后返回到根节点后也把根节点加入这个序列中，这样就定义了一个与 dfs 一一对应的搜索序列！而且这个 搜索序列，也是所有点的一个排列。
对于一棵有根树（结点标号 1 到 n，以 1 为根），咕咕对它跑了一遍 dfs 得到了搜索序列后，它准备把这个序 列抄在纸上拿给咸鱼看。但是，粗心的咕咕在抄这个序列的时候，一些点被它忽略了，纸上的序列只有 m 个 点。待咸鱼看到纸上这个序列后，咸鱼就很好奇：咕咕那么粗心，只是抄少了点这么简单吗，会不会同时把 一些点的位置也给变化了呢？
现在，聪明的你，你能判断出来咕咕在抄的时候有没有把点的位置变化了吗？也就是说，咕咕给的 m 个点的 序列，真的能够由一个 dfs 得到的搜索序列删除几个点后得到吗？
输入
第一行一个整数 T(1≤ T ≤106)，表示有 T 组数据。
对于每组数据：
第一行有两个正整数 n 和 m(1≤m≤n≤106)，表示树的点数和咕咕给的序列的点数。
第二行有 n−1 个正整数 a1,a2,··· ,an−1(1≤ ai ≤i)，表示点 ai 是点 (i+1) 的父结点。
第三行有 m 个互不相同的正整数，b1,b2,··· ,bm(1≤bi ≤n)，表示咕咕给的序列。
输入保证同一个测试点下的所有数据的 n 的和不超过 106。
输出
对每一组数据，输出一行。如果一定不能得到，输出 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) 是没有办法 由任意一个搜索序列只通过删除点得到的。

假定给出的序列是合法序列，根据出现顺序， 重新排列整颗数的遍历次序，得到dfs序
去和给出的序列匹配，判别是否一致

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
const int M = 500000;
typedef long long LL;
const LL mod = 20180520;
const int maxt=1000000000;
int  a[N], b[N], id[N], nxt[N];
vector<int>p[N];
void dfs(int u)
{for(int it:p[u]){dfs(it);id[u]=min(id[u],id[it]);}return ;
}
int cnt;
void dfs2(int u)
{for(int it:p[u]){dfs2(it);}nxt[++cnt]=u;return ;
}
int cmp(int x,int y)
{return id[x]<=id[y];
}
int main()
{int t;scanf("%d", &t);while(t--){int n, m;scanf("%d %d", &n, &m);for(int i=1;i<=n;i++)p[i].clear(),id[i]=maxt;for(int i=2;i<=n;i++){int x;scanf("%d", &x);p[x].push_back(i);}int flag=0;for(int i=1;i<=m;i++)scanf("%d", &a[i]),id[a[i]]=i;dfs(1);for(int i=1;i<=n;i++)sort(p[i].begin(),p[i].end(),cmp);cnt=0;dfs2(1);int tot=1;for(int i=1;i<=m;i++){while(tot<=n&&nxt[tot]!=a[i])tot++;}if(tot>n)puts("BAD GUGU");else puts("NOT BAD");}return 0;
}