1004. 搭积木

题目描述

小 W 正在用积木搭建一个巨大的结构。有 n 块积木，编号为 1 到 n。第 i 块积木有两个整数属性 ai 和 bi。

一开始，小 W 打算一块一块地搭建。对每块积木 i，给定一个积木 fi

，表示积木 i 必须直接放在积木 fi 的上方。如果 fi = 0，则积木 i 位

于整个结构的最底部。题目保证这些要求是自洽的，并且最终会形成一个包含所有积木的完整结构。后来，小 W 觉得逐块搭建太无聊了。他想到一种新方法：可以先把若干块积木组装成一个结构，再一次性把整个已组装结构放到另一个结构上。具体地，对于两个不交的连通集合 A 和 B，若 A 中存在唯一的点 x 使得 fx ∈ B，那么 A 就可以被放在 B 的上面。

也就是说，在满足所有原始直接上下关系的前提下，小 W 可以自由选择执行放置操作的顺序，也可以提前组装某些局部结构。一次放置操作中，假设一个已经组装好的结构被放到另一个结构的上方。令：

• A 为上方结构内所有积木的 ai 之和；

• B 为下方承托结构内所有积木的 bi 之和。

这次放置操作的代价定义为 A × B。操作完成后，两个结构会合并为一个更大的结构。注意，下方承托结构指的是当前已经组装在一起的整个结构，而不只是单块积木或它的祖先。小 W 想知道，在所有合法的搭建顺序中，最小总代价是多少。

输入格式

本题单个测试点内有多组测试数据。第一行输入一个正整数 T (1 ≤ T ≤ 20)，表示测试数据组数。接下来按如下格式输入 T 组数据：第一行输入一个整数 n (1 ≤ n ≤ 2 × 105 )，表示积木数量。保证单个测试点内所有测试数据的 n 之和不超过 106。第二行输入 n 个整数 a1, a2, …, an (1 ≤ ai ≤ 103 )。

第三行输入 n 个整数 b1, b2, …, bn (1 ≤ bi ≤ 103 )。

第四行输入 n 个整数 f1, f2, …, fn。其中 f1 = 0，对于所有 i > 1，

保证 1 ≤ fi < i。

输出格式

对于每组数据，输出一行一个整数，表示搭建完整结构所需的最小总代价。

样例输入

1
3
3 10 1
5 1 10
0 1 1

样例输出

56

提示

样例中，积木 2 和 3 都必须直接放在积木 1 上方。

如果先把积木 2 放到积木 1 上，代价为 10 × 5 = 50。此时下方结构包含积木 {1, 2}，其 b 之和为 5 + 1 = 6。再放置积木 3，代价为 1 × 6 = 6。总代价为 50 + 6 = 56，可以证明这是最优的。本题输入量较大，建议使用较快速的输入方式（如关闭流同步的cin）。

来源：官方题面 PDF（2026"钉耙编程"暑期联赛 第1场）