46 lines
934 B
C++
46 lines
934 B
C++
// 115 not finished
|
|
#include <bits/stdc++.h>
|
|
using namespace std;
|
|
int n;
|
|
int a[1005];
|
|
int fa[1005];
|
|
int dt[1005];
|
|
int root;
|
|
vector<int> chi[1005];
|
|
bool ran[1005];
|
|
int ans, T;
|
|
void dfs(int now) // 染色到dt[now]
|
|
{
|
|
if (dt[now] == root)
|
|
{
|
|
ran[now] = 1, ans += (T++) * a[dt[now]];
|
|
return;
|
|
}
|
|
if (!ran[fa[dt[now]]])
|
|
dfs(fa[dt[now]]);
|
|
ran[now] = 1, ans += (T++) * a[dt[now]];
|
|
}
|
|
int main()
|
|
{
|
|
scanf("%d", &n);
|
|
for (int i = 1; i <= n; ++i)
|
|
scanf("%d", &a[i]), dt[i] = i;
|
|
sort(dt + 1, dt + n + 1, [](int x, int y)
|
|
{ return a[x] < a[y]; });
|
|
for (int u, v, i = 1; i < n; ++i)
|
|
scanf("%d%d", &u, &v),
|
|
fa[v] = u, chi[u].push_back(v);
|
|
for (int i = 1; i <= n; ++i)
|
|
{
|
|
if (fa[i] == i)
|
|
{
|
|
root = i;
|
|
break;
|
|
}
|
|
}
|
|
for (int i = 1; i <= n; ++i)
|
|
{
|
|
dfs(i);
|
|
}
|
|
printf("%d\n", ans);
|
|
} |