#include <bits/stdc++.h>
using namespace std;

void dfs(int x, int parent, vector < vector <int> > &vertex, vector <long long> &police, vector <long long> &with,vector <long long> &out)
{
    long long N = 0, MinN = police[x];
    for(int i=0; i<vertex[x].size(); i++)
    {
        if(vertex[x][i]!=parent)
        {
            dfs(vertex[x][i],x,vertex,police,with,out);
            N += with[vertex[x][i]];
            MinN += min(with[vertex[x][i]],out[vertex[x][i]]);
        }
    }
    with[x] = MinN;
    out[x] = N;
//    cout<<"DFS!!!"<<x<<" ";
//    cout<<MinN<<" "<<N<<endl;
}

void dfs_no2(int x,int parent,vector < vector <int> > &vertex, vector <bool> &place_police, vector <long long> &with,vector <long long> &out)
{
    if(!place_police[x])
    {
        if(with[x]<=out[x])
        {
            place_police[x] = true;
        }
        else
        {
            for(int i=0; i<vertex[x].size(); i++)
            {
                place_police[vertex[x][i]] = true;
            }
        }
    }
    for(int i=0; i<vertex[x].size(); i++)
    {
        if(vertex[x][i]!=parent)
        {
            dfs_no2(vertex[x][i],x,vertex,place_police,with,out);
        }
    }
}
int main()
{
    int Z;
    cin>>Z;
    while(Z--)
    {
        int N;
        cin>>N;
        vector <long long> police;
        vector<long long> with(N,0);
        vector<long long>out(N,0);
        for(int i=0; i<N; i++)
        {
            int x;
            cin>>x;
            police.push_back(x);
        }
        vector < vector <int> > vertex(N,vector<int>());
        vector <bool> place_police(N,false);
        for(int i=0; i<N-1; i++)
        {
            int x1,y1;
            cin>>x1>>y1;
            x1--;
            y1--;
            vertex[x1].push_back(y1);
            vertex[y1].push_back(x1);
        }
        dfs(0,-1,vertex,police,with,out);
//        for(int i=0;i<N;i++)
//        {
//            cout<<i<<"with: "<<with[i]<<"out: "<<out[i]<<endl;
//        }
        long long mini = min(with[0],out[0]);
        cout<<mini<<endl;
        dfs_no2(0,-1,vertex,place_police,with,out);
        for(int i=0;i<place_police.size();i++)
        {
            cout<<place_police[i];
        }
        cout<<endl;
    }
}