#include <bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define fi first
#define si second
#define pii pair<int,int>
#define int long long

using namespace std;

const int maxn=2*1e5+10;

int parent[maxn];
vector<int>graf[maxn];
vector<int>niz(maxn);
vector<int>c1,c2;

void oboj(int nod,int p,bool c){
    if(c)c1.push_back(nod);
    else c2.push_back(nod);
    for(auto i:graf[nod]){
        if(i==p)continue;
        oboj(i,nod,!c);
    }
}

signed main()
{
    speed;
    bool sluc2=1,sluc3=1;
    int n;
    int sum1=0,sumall=0;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>niz[i];
        sumall+=niz[i];
        if(i!=1&&niz[i]!=niz[i-1])sluc3=0;
    }
    for(int i=1;i<n;i++){
        int a,b,u,v;
        cin>>a>>b;
        u=min(a,b);
        v=max(a,b);
        if(u+1!=v)sluc2=0;
        graf[u].push_back(v);
        graf[v].push_back(u);
    }
    if(graf[1].size()==n-1){
        sum1=niz[1];
        for(int i=1;i<n;i++){
            int u,v;
            cin>>u>>v;
        }
        if(sum1<=sumall-sum1){
            cout<<sum1<<endl;
            cout<<1<<endl<<1<<endl<<0<<endl;
        }
        else{
            cout<<sumall-sum1<<endl;
            cout<<n-1<<endl;
            for(int i=2;i<=n;i++)cout<<i<<" ";
            cout<<endl<<0<<endl;
        }
    }
    else if(sluc3){
        oboj(1,1,true);
        if(c1.size()<=c2.size()){
            cout<<niz[1]*c1.size()<<endl;
            cout<<c1.size()<<endl;
            for(auto i:c1)cout<<i<<" ";
            cout<<endl<<0<<endl;
        }
        else{
            cout<<niz[1]*c2.size()<<endl;
            cout<<0<<endl;
            cout<<c2.size()<<endl;
            for(auto i:c2)cout<<i<<" ";
        }
    }
    else if(sluc2){
        vector<int>dp(n+10,0);
        dp[1]=niz[1];
        for(int i=2;i<=n;i++){
            if(dp[i-1]<dp[i-2]){
                parent[i]=i-1;
                dp[i]=dp[i-1]+niz[i];
            }
            else{
                parent[i]=i-2;
                dp[i]=dp[i-2]+niz[i];
            }
        }
        vector<int>red,blue;
        if(dp[n]<=dp[n-1]){
            cout<<dp[n]<<endl;
            int nod=n;
            while(parent[nod]!=0){
                if(nod%2)blue.push_back(nod);
                else red.push_back(nod);
                nod=parent[nod];
            }
            if(nod%2)blue.push_back(nod);
            else red.push_back(nod);
            cout<<red.size()<<endl;
            for(auto i:red)cout<<i<<" ";
            if(red.size()!=0)cout<<endl;
            cout<<blue.size()<<endl;
            for(auto i:blue)cout<<i<<" ";
        }
        else{
            cout<<dp[n-1]<<endl;
            int nod=n-1;
            while(parent[nod]!=0){
                if(nod%2)blue.push_back(nod);
                else red.push_back(nod);
                nod=parent[nod];
            }
            if(nod%2)blue.push_back(nod);
            else red.push_back(nod);
            cout<<red.size()<<endl;
            for(auto i:red)cout<<i<<" ";
            if(red.size()!=0)cout<<endl;
            cout<<blue.size()<<endl;
            for(auto i:blue)cout<<i<<" ";
        }
    }
    return 0;
}