---

题目：

传送门

---

分析：

我们直接放上合并果子的代码，然后怒切$..$
好吧，其实是我找不到证明$ta$是哈夫曼树的过程，但题解说是合并果子，所以就^ _ ^

---

代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
#define LL long long
using namespace std;
inline LL read() {LL d=0,f=1;char s=getchar();while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}while(s>='0'&&s<='9'){d=d*10+s-'0';s=getchar();}return d*f;
}
LL x[200005],y[200005];
int main()
{LL q=read();while(q--){LL n=read();fill(x,x+200000,0x3f3f3f3f);fill(y,y+200000,0x3f3f3f3f);for(LL i=1;i<=n;i++) x[i]=read();sort(x+1,x+1+n);LL ans=0;LL h1=1,h2=1,k=1,nn=0,w;while(k<n){if (x[h1]<y[h2]) {w=x[h1];h1++;}else {w=y[h2];h2++;}if (x[h1]<y[h2]) {w+=x[h1];h1++;}else {w+=y[h2];h2++;}y[++nn]=w;ans+=w;k++;}printf("%lld\n",ans);}return 0;
}