#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using str = string;
using pi = pair<int,int>;
using pl = pair<ll,ll>;
using vb = vector<bool>;
using vi = vector<int>;
using vl = vector<ll>;
using vpl = vector<pl>;
using vvi = vector<vi>;
using vvl = vector<vl>;
#define f first
#define s second
#define pb push_back
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define sor(x) sort(all(x))
#define lb lower_bound
#define sz(x) int((x).size())
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

void solve(){
    int n;
    cin >> n;
    vi v(n + 1);
    F0R(i, n)cin >> v[i + 1];
    vvi l(n + 1);
    F0R(i, n - 1){
        int u, v;
        cin >> u >> v;
        l[u].pb(v);
        l[v].pb(u);
    }
    vi a(n), b(n);
    queue<pi> q;
    vb visited(n + 1);
    vvi ranksa(n + 1), ranksb(n + 1);
    q.push({1, 0});
    visited[1] = 1;
    int mx = 0;
    while(!q.empty()){
        int c = q.front().f, rank = q.front().s;
        q.pop();
        visited[c] = 1;
        a[rank] += v[c];
        mx = rank;
        ranksa[rank].pb(c);
        int cnt = 0;
        trav(el, l[c]){
            if(visited[el])continue;
            q.push({el, rank + 1});
            cnt++;
        }
        if(cnt == 0) b[rank] += v[c];
        else ranksb[rank].pb(c);
    }
    vl dp(mx + 1);
    a.resize(mx + 1);b.resize(mx + 1);
    if(mx <= 1){
        cout << 0 << "\n";
        cout << 0 << "\n\n";
        cout << 0 << "\n";
        return;
    }
    dp[0] = a[0];
    dp[1] = a[1] + min(a[0] - b[1], 0);
    FOR(i, 2, mx + 1) dp[i] = a[i] + min(dp[i - 1] - b[i], dp[i - 2]);
    cout << min(dp[mx], dp[mx - 1]) << "\n";
    int cur = mx - 1;
    vi parn, neparn;
    if(dp[mx] < dp[mx - 1])cur = mx;
    while(cur > 1){
        if(cur % 2){
            if(dp[cur - 1] - b[cur] < dp[cur - 2]){
                trav(el, ranksb[cur]) neparn.pb(el);
                cur--;
            }
            else{
                trav(el, ranksa[cur]) neparn.pb(el);
                cur -= 2;
            }
        }
        else{
            if(dp[cur - 1] - b[cur] < dp[cur - 2]){
                trav(el, ranksb[cur]) parn.pb(el);
                cur--;
            }
            else{
                trav(el, ranksa[cur]) parn.pb(el);
                cur -= 2;
            }
        }
    }
    if(cur == 1){
        if(a[0] - b[1] < 0){
            trav(el, ranksb[cur]) neparn.pb(el);
            cur--;
        }
        else
            trav(el, ranksa[cur]) neparn.pb(el);
    }
    if(cur == 0)trav(el, ranksa[cur]) parn.pb(el);
    cout << sz(parn) << "\n";
    trav(el, parn)cout << el << " ";
    cout << "\n";
    cout << sz(neparn) << "\n";
    trav(el, neparn)cout << el << " ";
    cout << "\n";

}


int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int t; t = 1;while(t--){
        solve();
    }
    return 0;
}