seuOJ497 - 大力出奇迹

• 题目类型：传统
• 输入文件：标准输入流
• 输出文件：标准输出流
• 时间限制：4000 ms
• 空间限制：1024 MiB
• 题目标签：Div.2, 2024

题目描述

我至今仍然不知道他们 AK 的原因。

现在有两棵深度为 $n$ 的满二叉树，树上节点编号依次为 $1$ 到 $2^n-1$ ，定义根节点的深度为 $1$ ，则深度为 $k$ 的节点编号依次为 $2^{k-1}$ 到 $2^k-1$ 。

现在我们把第一棵树的所有叶子节点(深度为 $n$ 的节点)分别向第二棵树上的某个节点连一条边，准确来说，第一棵树上编号为 $2^{n-1}+i$ 的叶子节点将会向第二棵树上编号为 $a_i$ 的节点连一条特殊的无向边。

在这两棵树和新加的边构成的无向图里，我们定义一个简单环为不重复经过同一节点且刚好经过两次特殊边的环，一个简单环的长度定义为环内的节点数。

现在请你回答最长简单环的长度，如果不存在简单环，输出 $0$。

输入格式

第一行输入一个整数 $n(1\leq n\leq 18)$ ，代表满二叉树的深度。

第二行输入 $2^{n-1}$ 个整数 $a_1,a_2,...,a_{2^{n-1}}(1\leq a_i\leq 2^n-1)$ ，代表第一棵树的叶子节点连到第二棵树的节点编号。

输出格式

输出最长简单环的长度。

样例

输入样例1

3
2 4 1 7

输出样例1

10

输入样例2

4
15 6 1 2 15 5 12 8

输出样例2

14

输入样例3

4
15 15 15 15 15 15 15 15

输出样例3

8

提示
样例 $1$ 如下：