## 题解

$$sz[u] \times w[v] + rest$$

$$sz[v]\times w[u] + rest$$

$$(\frac{w[v]}{sz[v]} – \frac{w[u]}{sz[u]})(sz[u]sz[v])<0$$

$Q.E.D.$

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<ctype.h>
#include<queue>
#include<map>
#define Re register
#define fo(i, a, b) for (Re int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (Re int i = (a); i >= (b); --i)
#define edge(i, u) for (Re int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define pb push_back
#define F first
#define S second
#define ll long long
#define inf 1000000007
#define mp std::make_pair
#define eps 1e-4
#define mod 10000000
#define lowbit(x) (x & -x)
#define N 1105
#define clr(arr) memset(arr, 0, sizeof arr)
#define bset std::bitset<N>
{
Re int x = 0; Re bool flag = 0; Re char ch = getchar();
while (!isdigit(ch) && ch != '-') ch = getchar();
if (ch == '-') flag = 1, ch = getchar();
while (isdigit(ch)) x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
if (flag) x = -x; return x;
}
int n, rt, head[N], tot, fa[N];
struct edge {
int nxt, v;
} e[N << 1];
inline void addedge (int u, int v)
{
}
struct node {
int sz, w, id;
friend bool operator < (node x, node y) { return x.w * y.sz < y.w * x.sz; }
};
std::priority_queue<node> q;
inline void dfs (int u, int F)
{
fa[u] = F;
edge (i, u)
{
if (v == F) continue;
dfs(v, u);
}
}
int sz[N], w[N], f[N], ans;
inline int find (int u) { return f[u] == u ? u : f[u] = find(f[u]); }
int main ()
{
{
ans = 0; tot = 0; clr(head); w[0] = sz[0] = 0;
fo (i, 1, n) w[i] = read(), f[i] = i, sz[i] = 1, ans += w[i];
fo (i, 2, n)
{
}
dfs(rt, 0);
fo (i, 1, n) if (rt != i) q.push((node) {1, w[i], i});
while (!q.empty())
{
node u = q.top(); q.pop();
if (u.sz != sz[u.id]) continue;
f[u.id] = find(fa[u.id]); ans += w[u.id] * sz[f[u.id]];
sz[f[u.id]] += sz[u.id]; w[f[u.id]] += w[u.id];
if (f[u.id]) q.push((node) {sz[f[u.id]], w[f[u.id]], f[u.id]});
}
printf("%d\n", ans);
}
return 0;
}