#P18226. Growing Tree

Growing Tree

Growing Tree

Little Q 种下了一棵树。最初,树上只有编号为 11 的根节点,它同时也是叶子。

每天上午,每个叶子节点 uu 都会长出两条新的枝干:

  • 一条连接节点 uu 与节点 2u2u,长度为 a2ua_{2u};
  • 另一条连接节点 uu 与节点 2u+12u+1,长度为 a2u+1a_{2u+1}。

之后,uu 不再是叶子,节点 2u2u 和 2u+12u+1 成为新的叶子。树会生长 nn 天,最终形成一棵有 2n+1−12^{n+1}-1 个节点、2n2^n 个叶子的满二叉树。

在这 nn 天中,每天下午,Little Q 可以选择一条已经长出来的枝干进行修剪,将它的长度改成任意正整数,也可以不修剪。新长度可以小于或大于原长度。

他希望树完全长成后,从根到每个叶子的简单路径上的枝干长度之和两两不同。

求最少需要修剪多少条枝干;如果无法做到,输出 −1-1。

输入格式

第一行包含一个整数 TT,表示测试用例数。

每个测试用例:

  • 第一行包含一个整数 nn,表示树生长的天数。
  • 第二行包含 2n+1−22^{n+1}-2 个整数 a2,a3,…,a2n+1−1a_2,a_3,\ldots,a_{2^{n+1}-1},其中 aua_u 表示连接节点 ⌊u/2⌋\lfloor u/2\rfloor 与节点 uu 的枝干的原始长度。

数据范围:

$$1\le T\le1000,\qquad 1\le n\le10,\qquad 1\le a_u\le10^8.$$

保证整个输入中 n>7n>7 的测试用例不超过 1010 个。没有另加所有节点数之和的限制。

原始长度的上界不限制修剪后的新长度;修剪后的长度只需是正整数。

输出格式

对于每个测试用例输出一行:若可以满足要求,输出最少需要修剪的枝干数;否则输出 −1-1。

样例

3
2
1 2 4 3 2 1
2
1 2 3 3 2 1
2
1 2 3 3 1 1
1
2
-1

样例说明

第一个测试用例中,原来的四条根到叶子的路径长度依次为 5,4,4,35,4,4,3。在第一天下午,将枝干 (1,2)(1,2) 的长度从 11 改为 1010,最终四条长度变成 14,13,4,314,13,4,3,因此只需修剪一条。

第二个测试用例原来的四条长度为 4,4,4,34,4,4,3。第一天下午将枝干 (1,2)(1,2) 的长度改为 1010,第二天下午再将枝干 (2,4)(2,4) 的长度改为 1010,四条长度变成 20,13,4,320,13,4,3,可以用两次修剪完成。

第三个测试用例中,两个叶子兄弟对的路径长度分别相同。要区分每一对兄弟,都必须修改其中一条在第二天上午才长出的末端枝干;但第二天下午只能修改一条,故无解。