Skip to content

1120: ⸮吗理合这

题目

题目描述

上完搜索课,老师给大家出了一道题,给定一棵$n$个点的有根树,根为$1$号点,现在要求同学们对它进行BFS,并输出BFS序

机智的小聪当即表示“这么大一棵树,不会真有人去验证结果的正确性吧,不会吧,不会吧”,当即交了一个随机排列,觉得自己不会被发现。然而,老师决定给小聪一个~~惊喜~~惊吓,他找到你这个编程高手,希望你可以对于任意给出的一个排列$a_i$,判断它是不是这棵树的合理BFS序

但你和小聪是好朋友,你可不想让小聪被逮住,所以你将会将结果以相反的形式输出,正确输出No,否则输出Yes!!!

如果你遗忘或不确定什么是BFS,那么可以参考以下伪代码

text 首先将根节点放入队列中 从队列中取出第一个节点 将它所有尚未遍历过的直接子节点加入队列中 若队列为空,表示搜索结束,不然回到步骤2

输入格式

第一行有一个数字,为 $n$ ,表示树的节点数

接下来$n-1$行描述这棵树的结构,每行一对$u$, $v$,表示在树中$u$是 $v$的父节点,保证$u<v$

接下来一行共$n$个数,表示$a_1,a_2,...,a_n$

输出格式

输出仅一行,一个字符串NoYes,表示是否为合理BFS序

样例输入

样例输入 1

text 4 1 2 1 3 2 4 1 2 3 4

样例输入 2

text 10 1 2 2 3 3 4 3 5 1 6 3 7 1 8 2 9 1 10 1 2 9 8 10 3 6 4 5 7

样例输出

样例输出 1

text No//因为它行,所以它不行

样例输出 2

text Yes//因为它不行,所以它行

数据范围

共有十个测试组,每个测试组中有若干测试点,通过一组内全部测试点方可得到该组分数,测试组的信息如下:

| 测试组名 | 分值 | 数据范围 | 特殊条件 | | :------: | :--: | :----------: | :-------------------------------------: | | $4$ | $10$ | $n\leq 5$ | 无 | | 月 | $10$ | $n\leq 10^3$ | 保证树是链(每点最多有$1$个子节点) | | $1$ | $10$ | $n\leq 10^3$ | 保证树是满二叉树 | | 日 | $10$ | $n\leq 10^3$ | 保证树是二叉树(每点最多有$2$个子节点) | | 愚 | $10$ | $n\leq 10^3$ | 无 | | 人 | $10$ | $n\leq 10^3$ | 无 | | 节 | $10$ | $n\leq 10^5$ | 保证树是满二叉树 | | 快 | $10$ | $n\leq 10^5$ | 保证树层数不超过$\log_2(n)$层 | | 乐 | $10$ | $n\leq 10^5$ | 无 | | $!$ | $10$ | $n\leq 10^5$ | 无 | | | | | |

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!