← 返回题目列表

Codeforces · 1919/D

D. 01 树

中文机器翻译题面 查看原题

有一个边加权完全二叉树,其叶子为$$$n$$$。完全二叉树被定义为每个非叶顶点恰好有 2 个子节点的树。对于每个非叶顶点,我们将其子节点之一标记为左子节点,将另一个标记为右子节点。

二叉树有一个非常奇怪的属性。对于每个非叶顶点,其子节点的一条边的权重为 $$$0$$$,而另一条边的权重为 $$$1$$$。请注意,权重 $$$0$$$ 的边可以连接到其左子节点或右子节点。

你忘记了树是什么样子,但幸运的是,你仍然记得一些关于叶子的信息,这些信息以数组 $$$a$$$ 的形式存在,大小为 $$$n$$$。对于从$$$1$$$到$$$n$$$的每个$$$i$$$,$$$a_i$$$表示从根到dfs顺序$$$^\ddagger$$$中的第$$$i$$$个叶子的距离$$$^\dagger$$$。判断是否存在满足数组$$$a$$$的完全二叉树。请注意,您不需要重建树。

$$$^\dagger$$$ 从顶点 $$$u$$$ 到顶点 $$$v$$$ 的距离定义为从顶点 $$$u$$$ 到顶点 $$$v$$$ 的路径上边的权重之和。

$$$^\ddagger$$$ 通过在二叉树的根上调用以下 $$$\texttt{dfs}$$$ 函数来找到叶子的 dfs 顺序。

输入

每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2\cdot 10^5$$$) — 数组 $$$a$$$ 的大小。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le n - 1$$$) - 从根到第 $$$i$$$ 叶子的距离。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^5$$$。

输出

对于每个测试用例,如果存在满足数组 $$$a$$$ 的完整二叉树,则打印“YES”,否则打印“NO”。

您可以在任何情况下打印每个字母(例如,“YES”、“Yes”、“yes”、“yEs”都将被识别为肯定答案)。

示例

输入 #1

2
5
2 1 0 1 1
5
1 0 2 1 3

输出 #1

YES
NO

注意

在第一个测试用例中,以下树满足数组。

在第二个测试用例中,可以证明不存在满足数组的完全二叉树。