小 W 正在用积木搭建一个巨大的结构。有 nn 块积木编号为 11 到 nn。第 ii 块积木有两个整数属性 aiai​ 和 bibi​。一开始小 W 打算一块一块地搭建。对每块积木 ii给定一个积木 fifi​表示积木 ii 必须直接放在积木 fifi​ 的上方。如果 fi0fi​0则积木 ii 位于整个结构的最底部。题目保证这些要求是自洽的并且最终会形成一个包含所有积木的完整结构。后来小 W 觉得逐块搭建太无聊了。他想到一种新方法可以先把若干块积木组装成一个结构再一次性把整个已组装结构放到另一个结构上。具体地对于两个不交的连通集合 AA 和 BB若 AA 中存在唯一的点 xx 使得 fx∈Bfx​∈B那么 AA 就可以被放在 BB 的上面。也就是说在满足所有原始直接上下关系的前提下小 W 可以自由选择执行放置操作的顺序也可以提前组装某些局部结构。一次放置操作中假设一个已经组装好的结构被放到另一个结构的上方。令AA 为上方结构内所有积木的 aiai​ 之和BB 为下方承托结构内所有积木的 bibi​ 之和。这次放置操作的代价定义为 A×BA×B。操作完成后两个结构会合并为一个更大的结构。注意下方承托结构指的是当前已经组装在一起的整个结构而不只是单块积木或它的祖先。小 W 想知道在所有合法的搭建顺序中最小总代价是多少。一、问题建模将n块积木视为节点父子关系f_i构成一棵以1为根的树f_i0表示i是根。每个节点i有两个权值a_i上方结构权值和和b_i下方结构权值和。操作选择一条边(u, fa_u)将u所在的连通块合并到fa_u所在的连通块代价为A_u × B_{fa_u}A_u是u连通块的a和B_{fa_u}是fa_u连通块的b和。目标最小化所有合并操作的总代价。二、贪心策略推导考虑同一父节点p的两个子节点x和y有两种合并顺序先合并x再合并y合并x代价A_x · B_p合并y此时p的b值变为B_p B_x代价A_y · (B_p B_x)总代价A_x B_p A_y (B_p B_x)先合并y再合并x总代价A_y B_p A_x (B_p B_y)两者相减Δ [A_x B_p A_y(B_pB_x)] - [A_y B_p A_x(B_pB_y)] A_y B_x - A_x B_y若Δ 0则先合并x更优若Δ 0则先合并y更优。等价于比较比值先合并 x 更优 ⇔ A_x / B_x A_y / B_y结论每次应优先合并A/B比值最大的连通块。三、算法流程初始化每个节点独立为一个连通块用并查集维护。将每个连通块(a_i, b_i, i)放入优先队列按a/b比值从大到小排序。循环合并取出队首连通块比值最大设其代表节点为u。若u已被合并过vis[u]1跳过。若u不是根fa[u] ≠ 0将其合并到父节点fa[u]的连通块累加代价ans b[代表(fa[u])] * a[u]并查集合并f[u] 代表(fa[u])更新父连通块的权值a[父] a[u],b[父] b[u]将更新后的父连通块重新入队。终止队列为空时所有节点合并完成ans即为最小总代价。四、关键细节1. 优先队列排序规则重载运算符实现按a/b降序排列bool operator(node a, node b) { if (1LL * a.a * b.b 1LL * a.b * b.a) { // 比值相等时按编号或a值稳定排序 if (a.u b.u) return a.a b.a; return a.u b.u; } return 1LL * a.a * b.b 1LL * a.b * b.a; // 注意用交叉相乘避免浮点数误差 }为什么不用浮点数​浮点数可能有精度误差直接用a.a * b.b与a.b * b.a比较更安全。2. 并查集的作用每个连通块用其根节点作为代表元。合并后子节点的代表元指向父节点确保后续操作时能找到正确的连通块权值。3. 避免重复处理vis[u]标记节点是否已合并到父节点。由于合并后父节点权值更新父节点会以新状态重新入队旧状态会被vis过滤。五、复杂度分析每个节点最多入队、出队各一次优先队列操作O(log n)。并查集操作近似O(α(n))α为反阿克曼函数。总时间复杂度O(n log n)适合n ≤ 2×10^5。六、示例模拟假设输入n3 a[1,2,3] b[3,2,1] fa[0,1,1] // 1是根2和3是1的子节点初始队列(1/3, 节点1),(2/21, 节点2),(3/13, 节点3)→ 按比值排序节点3(3), 节点2(1), 节点1(1/3)。取出节点3合并到父节点1代价b[1] * a[3] 3 * 3 9更新a[1]134,b[1]314节点1重新入队(4/41, 节点1)取出节点2合并到父节点1代价b[1] * a[2] 4 * 2 8更新a[1]426,b[1]426队列剩余节点1已合并子节点但根节点无需再合并结束。总代价9 8 17。题解#includebits/stdc.h using namespace std; #define mk make_pair #define MID int mid(lr)1; #define ll long long #define endl \n #define siz(a) int(a.size()) int n,tot,fa[200100],vis[200100],f[200100],a[200100],b[200100]; struct node{ int a,b,u; }; bool operator(node a,node b){ if(1ll*a.a*b.b1ll*a.b*b.a){ if(a.ub.u)return a.ab.a; return a.ub.u; } return 1ll*a.a*b.b1ll*a.b*b.a; } int fi(int x){ if(f[x]x)return x; return f[x]fi(f[x]); } void solve(){ cinn; for(int i1;in;i){ cina[i]; } for(int i1;in;i){ cinb[i]; } for(int i1;in;i){ cinfa[i]; } priority_queuenodeq; for(int i1;in;i){ f[i]i; vis[i]0; q.push(node{a[i],b[i],i}); } ll ans0; while(!q.empty()){ node tmpq.top();q.pop(); int utmp.u; if(vis[u])continue; vis[u]1; if(fa[u]){ int vfi(fa[u]); ans1ll*b[v]*a[u]; f[u]v; a[v]a[u]; b[v]b[u]; q.push(node{a[v],b[v],v}); } } coutansendl; } int main(){ ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); int TTT; cinTTT; while(TTT--)solve(); }