#include <iostream>
#include <vector>
#include <map>
#include <set>

using namespace std;

struct vertices {
    std::vector<int> neighbors_of(int v1) {
        return neighbors[v1 - 1];
    }
    void add_neighbors(int v1, int v2) {
        neighbors[v1 - 1].push_back(v2);
        neighbors[v2 - 1].push_back(v1);
    }

    vertices(int n) {
        neighbors = vector<vector<int>>(n);
    }

    private:
    vector<vector<int>> neighbors;
};

struct path {
    int max_weight;
    std::set<int> vertices;
};

struct paths_of_length {
    void add_path(int v1, int v2, const path& p) {
        if (v1 > v2) std::swap(v1, v2);
        if (paths.count({v1, v2})) return;
        paths[{v1, v2}] = p;
    }

    path& get_path(int v1, int v2) {
        if (v1 > v2) std::swap(v1, v2);
        return paths[{v1, v2}];
    }

    // vertices + max weight vertex on path between them
    // vertices should be in ascending order
    std::map<std::pair<int, int>, path> paths;
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vertices g = vertices(N);

    std::vector<int> weights(N);
    for (int i = 0; i < N; i++) {
        std::cin >> weights[i];
    }

    // length = index + 1
    std::vector<paths_of_length> dp;
    dp.push_back(paths_of_length());

    for (int i = 0; i < N - 1; i++){
        int v1, v2;
        cin >> v1 >> v2;
        g.add_neighbors(v1, v2);
        dp[0].add_path(v1, v2, path{max(weights[v1 - 1], weights[v2 - 1]), {v1, v2}});
    }

    bool added_new = true;
    int j = 1;
    while (added_new) {
        dp.push_back(paths_of_length());
        added_new = false;

        for (const auto& [key, path] : dp[j - 1].paths) {
            for (int next_vertex : g.neighbors_of( key.first)) {
                // add neighbor if it isn't in the path already
                if (!path.vertices.count(next_vertex)) {
                    added_new = true;
                    auto new_vertices = path.vertices;
                    new_vertices.insert(next_vertex);
                    dp[j].add_path(key.second, next_vertex, {max(weights[next_vertex - 1], path.max_weight), new_vertices});
                }
            }

            for (int next_vertex : g.neighbors_of( key.second)) {
                if (!path.vertices.count(next_vertex)) {
                    added_new = true;
                    auto new_vertices = path.vertices;
                    new_vertices.insert(next_vertex);
                    dp[j].add_path(key.first, next_vertex, {max(weights[next_vertex - 1], path.max_weight), new_vertices});
                }
            }
        }

        j++;
    }

    unsigned long beauty = 0;
    for (unsigned long i = 0; i < dp.size(); i ++) {
        for (const auto& [whatever, path] : dp[i].paths) {
            beauty += path.max_weight * (i + 1);
        }
    }

    std::cout << beauty;

    return 0;
}