Yandex algo, round 1, task e

// Copyright (C) 2016 Sayutin Dmitry.
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License as
// published by the Free Software Foundation; version 3

// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License
// along with this program; If not, see <http://www.gnu.org/licenses/>.

#include <iostream>
#include <vector>
#include <stdint.h>
#include <algorithm>
#include <set>
#include <map>
#include <array>
#include <queue>
#include <stack>
#include <functional>
#include <utility>
#include <string>
#include <assert.h>
#include <iterator>

using std::cin;
using std::cout;
using std::cerr;

using std::vector;
using std::map;
using std::array;
using std::set;
using std::string;

using std::pair;
using std::make_pair;

using std::min;
using std::abs;
using std::max;

using std::sort;
using std::generate;
using std::min_element;
using std::max_element;

template <typename T>
T input() {
    T res;
    cin >> res;
    return res;
}

#ifdef LOCAL
#define LASSERT(X) assert(X)
#else
#define LASSERT(X) {}
#endif

struct entry {
    char type; // 0 - down, 1 - up,
    size_t newv;
};

vector<size_t> euler;
vector<pair<size_t, size_t>> times; // [).
vector<vector<size_t>> seg;
vector<entry> LOG;

void dfs(size_t v, const vector<vector<size_t>>& graph, vector<char>& vis) {
    vis[v] = true;
    times[v].first = euler.size();

    for (size_t u: graph[v])
        if (not vis[u]) {
            LOG.push_back(entry {0, u});
            dfs(u, graph, vis);
            LOG.push_back(entry {1, v});
        }

    euler.push_back(v);
    times[v].second = euler.size();
}

void build_seg(size_t id, size_t l, size_t r) {
    if (l == r - 1) {
        seg.resize(max(seg.size(), id + 1));
        seg[id] = {euler[l]};
    } else {
        size_t mid = l + (r - l) / 2;
        build_seg(2 * id + 1, l, mid);
        build_seg(2 * id + 2, mid, r);

        seg[id].resize(r - l);
        std::merge(seg[2 * id + 1].begin(), seg[2 * id + 1].end(), seg[2 * id + 2].begin(), seg[2 * id + 2].end(), seg[id].begin());
    }
}

size_t count(size_t id, size_t nl, size_t nr, size_t l, size_t r, size_t a, size_t b) {
    if (l <= nl and nr <= r) {
        return std::upper_bound(seg[id].begin(), seg[id].end(), b) - std::lower_bound(seg[id].begin(), seg[id].end(), a);
    } else if (nr <= l or r <= nl) {
        return 0;
    } else {
        size_t mid = nl + (nr - nl) / 2;
        return count(2 * id + 1, nl, mid, l, r, a, b)
            + count(2 * id + 2, mid, nr, l, r, a, b);
    }
}

int main() {
    std::iostream::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    size_t n = input<size_t>();
    vector<vector<size_t>> tree(n);

    vector<size_t> prio(n);
    std::generate(prio.begin(), prio.end(), input<size_t>);

    for (size_t i = 1; i != n; ++i) {
        size_t v, u;
        cin >> v >> u;
        --v, --u;
        tree[v].push_back(u);
        tree[u].push_back(v);
    }

    vector<char> vis(n, false);
    euler.reserve(n);
    times.resize(n);

    dfs(0, tree, vis);
    for (auto& v: euler)
        v = prio[v];

    build_seg(0, 0, n);

    pair<size_t, size_t> ans = {0, 0}; // inv, root.
    size_t invroot = 0;
    for (size_t v = 0; v != n; ++v) {
        invroot += count(0, 0, n, times[v].first, times[v].second, prio[v] + 1, SIZE_MAX);
    }

//    cout << invroot << "\n";
    ans = {invroot, 0};
    size_t curroot = 0;
    for (size_t i = 0; i != LOG.size(); ++i) {
        size_t upper;
        size_t lower;
        size_t newroot = LOG[i].newv;

        if (LOG[i].type == 0)
            upper = curroot, lower = newroot;
        else
            upper = newroot, lower = curroot;

        size_t up_effect = count(0, 0, n, times[lower].first, times[lower].second, prio[upper] + 1, SIZE_MAX);
        size_t lo_effect = count(0, 0, n, 0, n, prio[lower] + 1, SIZE_MAX)
            - count(0, 0, n, times[lower].first, times[lower].second, prio[lower] + 1, SIZE_MAX);

        if (LOG[i].type == 1) {
            invroot += up_effect;
            invroot -= lo_effect;
        } else {
            invroot += lo_effect;
            invroot -= up_effect;
        }

        curroot = newroot;
        ans = min(ans, {invroot, curroot});
    }

    cout << ans.second + 1 << " " << ans.first << "\n";

    return 0;
}