提供一种基于贪心的解法。
首先是将 \(p\) 从小到大排序
考虑到该系统是一棵树，所以对于系统中的每个点，我们记：
\(tr_{son}\) 表示该点(目录)的儿子的位置
\(tr_{fa}\) 表示该点(目录)的父亲的位置
\(tr_{siz}\) 表示该点(目录)包含的点的个数
\(tr_{cnt}\) 表示该点(目录)有多少个儿子
\(tr_{val}\) 表示该点(目录)的 \(p\) 值
考虑对于现在系统中已经有了 \(x\) 个文件，现在要插入第 \(x+1\) 个文件。
考虑这个文件可以插入到的地方以及对答案贡献：
操作 \(1\)、插入到原有目录中。
贡献为：\((\sum\limits_{pos \in tr} tr_{val} \times (tr_{siz}*2+1))+p_{pos}\)
即新文件所有父亲目录的 \(p_i\) 乘上两倍该目录的点的个数加一，然后再加上新文件的 \(p_i\)
操作 \(2\)、将该位置的文件变成目录，然后向这个目录中插入原位置文件和新文件。
贡献为：\((\sum\limits_{pos \in tr} tr_{val} \times (tr_{siz}*2+1))+p_1+p_2+p_{pos} \times 3\)
即该位置文件所有父亲目录的 \(p_i\) 乘上两倍该目录的点的个数加一，然后加上该文件的 \(p_i\) 乘三，再加上 \(p_1\) 和 \(p_2\)
这些不难推导，可以结合样例推导
考虑其正确性：
1、若要将新文件插入到一个目录，一定会将新文件插在 \(p_i\) 尽量小的地方，而将 \(p\) 从小到大排序之后，一定会先插完 \(p_{1 \sim i-1}\)，再插 \(p_i\)
2、对于一个空位置，新文件一定是直接插在该位置比在该位置建目录，再插入到目录中更优
3、无论是插入到哪里，设该次插入对答案造成的贡献为 \(t\)，则新的可以插入的位置对答案造成的贡献不会小于 \(t\)
对于第三个性质的证明，我们只在整理将先进行操作 \(2\) 再进行操作 \(1\) 仍满足性质 \(3\)：
若再新建的目录下插入第 \(3\) 个文件，则相比操作二， \(\sum\) 中多出来的就是 \(p_{pos} \times (pos_{siz}+1)\) 即，\(p_{pos} \times 5\)，而再加上 \(p_3\)，显然 \(p_{pos} \times 5+p_3>p_{pos} \times 3 p_1+p_2\)
其他同理
基于这三个性质，我们可以如此操作：
对该系统进行深搜。
对于一个目录，考虑它可以加入的最小的 \(p_i\) 对答案的贡献，加入数组 \(a\) 中
对于一个文件，考虑它变成目录再插入文件对答案的贡献，加入数组 \(a\) 中
然后将 \(a\) 从小到大排序
将最小的加入答案，并更改该系统即可
注意特别判断在 \(root\) 插入的情况
上代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,k,p[N],ans;
struct jgt
{
int son[155];
int siz,val,cnt,fa;
}tr[N*2];
int tot;
struct jgt1
{
int x,pos;
}a[N*2];
int idx;
bool cmp(jgt1 t1,jgt1 t2)
{
return t1.x<t2.x;
}
void dfs(int wz,int sum)
{
if(wz==0)
{
for(int i=1;i<=tr[wz].cnt;i++)
dfs(tr[wz].son[i],0);
if(tr[wz].cnt!=k)
{
a[++idx].pos=wz;
a[idx].x=p[tr[wz].cnt+1];
}
}
else
{
if(tr[wz].cnt==0)
{
a[++idx].pos=wz;
a[idx].x=sum+tr[wz].val*3+p[1]+p[2];
}
else if(tr[wz].cnt==k)
{
for(int i=1;i<=k;i++)
dfs(tr[wz].son[i],sum+tr[wz].val*(tr[wz].siz*2+1));
}
else
{
a[++idx].pos=wz;
a[idx].x=sum+tr[wz].val*(tr[wz].siz*2+1)+p[tr[wz].cnt+1];
for(int i=1;i<=tr[wz].cnt;i++)
dfs(tr[wz].son[i],sum+tr[wz].val*(tr[wz].siz*2+1));
}
}
}
void get(int wz)
{
tr[wz].siz++;
if(tr[wz].fa!=0) get(tr[wz].fa);
}
void add(int wz)
{
if(wz==0)
{
tr[wz].cnt++;
int shu=tr[wz].cnt;
tr[wz].son[shu]=++tot;
tr[tot].val=p[shu];
tr[tot].fa=wz;
return ;
}
if(tr[wz].cnt!=0)
{
tr[wz].cnt++;
tr[wz].siz++;
int shu=tr[wz].cnt;
tr[wz].son[shu]=++tot;
tr[tot].val=p[shu];
tr[tot].fa=wz;
if(tr[wz].fa!=0) get(tr[wz].fa);
return ;
}
if(tr[wz].cnt==0)
{
tr[wz].cnt=2;
tr[wz].siz=2;
tr[wz].son[1]=++tot;
tr[tot].val=p[1];
tr[tot].fa=wz;
tr[wz].son[2]=++tot;
tr[tot].val=p[2];
tr[tot].fa=wz;
if(tr[wz].fa!=0) get(tr[wz].fa);
return ;
}
}
int main()
{
scanf("%d %d",&n,&k);
for(int i=1;i<=k;i++)
scanf("%d",&p[i]);
sort(p+1,p+k+1);
for(int i=1;i<=n;i++)
{
idx=0;
dfs(0,0);
sort(a+1,a+idx+1,cmp);
ans+=a[1].x;
add(a[1].pos);
}
printf("%d\n",ans);
return 0;
}