注意到每个点至少产生一次代价，而我们也可以让除了最小值以外的结点恰好仅产生一次代价，我们只需要以最小值为根每次删叶子即可做到，于是最小代价为 \(\sum_{i=1}^n a_i+(n-2)\min_{i=1}^n a_i\)。
接下来考虑计数，显然我们只关心一个点是不是最小值，我们不妨将最小值结点看作 \(1\)，否则看作 \(0\)。你发现只要一个连通块有最小值就一定能取到最小，或者只有一个孤立点也行。于是我们可以得到一个条件是，割完边两边的连通块要么是孤立点要么必须存在最小值。
不过这个条件其实是很丑的，我们根本无法对着它计数，考虑再仔细刻画一下。我们发现，对于每个 \(0\) 点的最后一个被割掉的边，需要保证在另一边存在 \(1\) 点。同时你观察该边连着的另一个点也需要满足这种情况。
我们不妨将每个点最后一个被割的边提出来变成一条有向边，从该点向外连。那么最后要求图变成以 \(1\) 点为根的内向树森林。
现在考虑计数。我们要对每个内向树森林统计有多少个连边方案。我们可以直接在树上进行子树 dp，考虑确定每棵子树内边的顺序再合并，而我们只需要记录往父亲连的那条边是哪种边以及处于子树内顺序的第几个即可。时间复杂度经过前缀和优化以及经典树上背包优化可以做到 \(\mathcal{O}(n^2)\)。