#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define F first
#define S second
#define Tsetso ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define pr pair < int , int >
const int N = 2e5+10,NN = 1005, length = 25 , mod = 1e9+7, inf = 1e9;
vector < int > g[N];
int color[N] , ans, n;
multiset< pair < int , int  > > *mst[N];
void dfs ( int node , int par )
{
    int mx = -1 ;
    for ( auto i : g[node])
    {
        if ( i == par)
            continue;
        dfs(i,node);
        if ( mx == -1)
                mx = i ;
        else if ( mst[i]->size() > mst[mx]->size())
            mx = i;
    }
    if ( mx == -1)
    {
        mst[node] = new multiset< pair < int , int > > ;
        mst[node]->insert({color[node],node});
        return ;
    }
    for ( auto i : g[node])
    {
        if ( i == par || i == mx)
            continue;
        for ( auto j : *mst[i])
                mst[mx]->insert(j);
    }
    auto it = mst[mx]->lower_bound({color[node],-1});
    while (it != mst[mx]->end() && it->first == color[node])
    {
        mst[mx]->erase(it);
        it =  mst[mx]->lower_bound({color[node],-1});
    }
    mst[node] = mst[mx];
    mst[node]->insert({color[node],node});
}
int main() {
    Tsetso
    cin >> n ;
    ans = n;
    for ( int i = 1 ; i <= n; i++)
        cin >> color[i];
    for ( int i = 1 ; i < n ; i++)
    {
        int u , v ;
        cin >> u >> v ;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1,0);
    set < int > s ;
    for ( auto j : *mst[1])
            s.insert(j.second);
    for ( auto j : s)
            cout << j << '\n';
}

//================code===================//

//#define TLE

#ifdef TLE
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#endif

#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <ctime>

#define ci(t) cin>>t
#define co(t) cout<<t
#define LL long long
#define ld long double
#define fa(i,a,b) for(LL i=(a);i<(LL)(b);++i)
#define fd(i,a,b) for(LL i=(a);i>(LL)(b);--i)
#define setp pair<pair<int,int>,int>
#define setl pair<LL,LL>
#define micro 0.000001

using namespace std;

LL gcd(LL a, LL b) { return a % b ? gcd(b, a % b) : b; }
LL lcm(LL a, LL b) { return (a * b) / gcd(a, b); }
#ifdef OHSOLUTION
#define ce(t) cerr<<t
#define AT cerr << "\n=================ANS=================\n"
#define AE cerr << "\n=====================================\n"
#else
#define AT
#define AE
#define ce(t)
#define __popcnt __builtin_popcountll
#endif

pair <int, int> vu[9] = { {0,1},{1,0},{0,-1} ,{-1,0},{0,0},{1,0}, {-1,1} , {1,-1},{-1,-1} }; //RDLU EWSN

template<typename T, typename U> void ckmax(T& a, U b) { a = a < b ? b : a; }
template<typename T, typename U> void ckmin(T& a, U b) { a = a > b ? b : a; }
struct gcmp { bool operator()(LL a, LL b) { return a < b; } bool operator()(setl a, setl b) { return a.second < b.second; } };
struct lcmp { bool operator()(LL a, LL b) { return a > b; } bool operator()(setl a, setl b) { return a.second > b.second; } };

const int max_v = 2e5 + 7;
const int INF = 1e9 + 7;
const LL LNF = (LL)5e18 + 7ll;
const LL mod = 1e9+7;

setl arr[max_v];
map<int, vector<int>> xh;
vector <int> vi[max_v];
map<setl, LL> dp;

LL dnq(int pos, int id)
{
	if (id == 0) return abs(pos);

	LL& ret = dp[{pos,id}];

	if (ret) return ret;

	if (vi[id - 1].size() == 1) return ret = dnq(vi[id - 1][0], id - 1)+ abs(pos-vi[id-1][0]);
	ret = LNF;
	LL dif = abs(vi[id - 1][0] - vi[id - 1][1]);
	ckmin(ret, dnq(vi[id - 1][1], id - 1) + dif + abs(pos - vi[id - 1][0]));
	ckmin(ret, dnq(vi[id - 1][0], id - 1) + dif + abs(pos - vi[id - 1][1]));
	return ret;
}

int main()
{
#ifdef OHSOLUTION
	freopen("input.txt", "r", stdin);
#endif	
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n; ci(n);
	fa(i, 0, n) ci(arr[i].first >> arr[i].second);

	vector <int> cod(n);

	fa(i, 0, n) cod[i] = arr[i].second;

	sort(cod.begin(), cod.end());
	cod.erase(unique(cod.begin(), cod.end()), cod.end());

	fa(i, 0, n) arr[i].second = lower_bound(cod.begin(), cod.end(), arr[i].second) - cod.begin();

	fa(i, 0, n) xh[arr[i].second].push_back(arr[i].first);

	for (auto& x : xh)
	{
		sort(x.second.begin(), x.second.end());
		vi[x.first].push_back(x.second[0]);
		if (x.second.size() > 1) vi[x.first].push_back(x.second.back());
	}
	

	co(dnq(0, cod.size()));
	return 0;
}
