#P18334. ICFC World Finals

ICFC World Finals

ICFC World Finals

一年一度的国际大学生桌上足球竞赛全球总决赛即将举行,你负责活动宣传,需要设计一张宣传横幅。为避免多余的细节,你决定横幅上只画比赛的晋级树。

今年的晋级树是一棵有 nn 个节点的满二叉树,每个内部节点恰好有两个孩子。每个节点对应两位选手之间的一场比赛,该场比赛的胜者晋级到父节点对应的比赛。根节点对应总决赛,胜者不再晋级。

横幅必须是边长为整数的矩形。晋级树必须按照以下规则画在横幅上:

  • 节点画成整点,可以位于横幅的边界上。坐标相对于横幅左上角确定。
  • 边是连接父子节点的直线段,与横幅的边平行。不同边不能交叉或重叠;有共同端点的边可以在该端点相接。
  • 对每个内部节点,必须把一个孩子画在它的右侧,另一个孩子画在它的下方,距离可以大于一个单位。结合边平行于矩形边的要求,前一个孩子与父节点的纵坐标相同、横坐标严格更大;后一个孩子与父节点的横坐标相同,并严格位于其下方。两个孩子中谁在右、谁在下可以自由决定。
  • 互不相交的子树,其包围盒也必须互不相交,包括边界也不能接触。 子树 TT 的包围盒 Box⁡(T)\operatorname{Box}(T),是包含它所有节点、各边与横幅边平行的最小闭矩形。子树互不相交指它们没有共同节点。

求能容纳这棵晋级树的横幅的最小面积。面积按矩形的实际边长相乘计算,不是矩形内的整点数量。

输入格式

第一行包含测试用例数 ZZ。

每组测试用例占两行。第一行包含节点数 nn。

第二行包含 n−1n-1 个整数,第 ii 个整数是节点 i+1i+1 的父节点编号。根节点为节点 11。输入保证给出一棵符合上述要求的满二叉树;不保证父节点编号小于孩子编号。

输出格式

对每组测试用例,输出一行一个整数,表示最小横幅面积。

数据范围

  • 1≤Z≤2000001\le Z\le200000;
  • 3≤n≤2000003\le n\le200000;
  • 所有测试用例的 nn 之和不超过 200000200000。

满二叉树的节点数必为奇数。因此范围内实际最大的合法 nn 为 199999199999,实际最多可同时出现 6666666666 组最小树;这两点是原条件的推论。

样例输入 1

2
5
1 1 3 3
9
1 1 2 2 3 3 6 6

样例输出 1

2
6

样例说明

第一组测试的一种最优摆放如下,面积为 22。

第一组样例的最优摆放

第二组测试的一种最优摆放如下,面积为 66。

第二组样例的最优摆放

下面的摆放虽然也占用面积 66,却不合法:以节点 22、33 为根的两棵子树没有共同节点,但它们的包围盒相交。

第二组样例的不合法摆放