#P18334. ICFC World Finals
ICFC World Finals
ICFC World Finals
一年一度的国际大学生桌上足球竞赛全球总决赛即将举行,你负责活动宣传,需要设计一张宣传横幅。为避免多余的细节,你决定横幅上只画比赛的晋级树。
今年的晋级树是一棵有 个节点的满二叉树,每个内部节点恰好有两个孩子。每个节点对应两位选手之间的一场比赛,该场比赛的胜者晋级到父节点对应的比赛。根节点对应总决赛,胜者不再晋级。
横幅必须是边长为整数的矩形。晋级树必须按照以下规则画在横幅上:
- 节点画成整点,可以位于横幅的边界上。坐标相对于横幅左上角确定。
- 边是连接父子节点的直线段,与横幅的边平行。不同边不能交叉或重叠;有共同端点的边可以在该端点相接。
- 对每个内部节点,必须把一个孩子画在它的右侧,另一个孩子画在它的下方,距离可以大于一个单位。结合边平行于矩形边的要求,前一个孩子与父节点的纵坐标相同、横坐标严格更大;后一个孩子与父节点的横坐标相同,并严格位于其下方。两个孩子中谁在右、谁在下可以自由决定。
- 互不相交的子树,其包围盒也必须互不相交,包括边界也不能接触。 子树 的包围盒 ,是包含它所有节点、各边与横幅边平行的最小闭矩形。子树互不相交指它们没有共同节点。
求能容纳这棵晋级树的横幅的最小面积。面积按矩形的实际边长相乘计算,不是矩形内的整点数量。
输入格式
第一行包含测试用例数 。
每组测试用例占两行。第一行包含节点数 。
第二行包含 个整数,第 个整数是节点 的父节点编号。根节点为节点 。输入保证给出一棵符合上述要求的满二叉树;不保证父节点编号小于孩子编号。
输出格式
对每组测试用例,输出一行一个整数,表示最小横幅面积。
数据范围
- ;
- ;
- 所有测试用例的 之和不超过 。
满二叉树的节点数必为奇数。因此范围内实际最大的合法 为 ,实际最多可同时出现 组最小树;这两点是原条件的推论。
样例输入 1
2
5
1 1 3 3
9
1 1 2 2 3 3 6 6
样例输出 1
2
6
样例说明
第一组测试的一种最优摆放如下,面积为 。

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

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