#include <iostream>
#include <vector>
#include <map>

//triangulacja == przykro mi

using namespace std;

typedef long long LL;

struct vertex
{
    vector<int> neighbours;
    int cost;
    vector<LL> results = { -1, -1 };
};

void input(vector<vertex>& g)
{
    int n;
    cin >> n;

    g.assign(n + 1, vertex());

    for (int i = 1; i < n + 1; i++)
    {
        int x;
        cin >> x;

        g[i].cost = x;
    }

    for (int i = 0; i < n - 1; i++)
    {
        int x, y;
        cin >> x >> y;

        g[x].neighbours.push_back(y);
        g[y].neighbours.push_back(x);
    }
}

LL dfs(vector<vertex>& g, vector<bool>& iG, int v, int a, bool gr) //a - ancestor, gr - guarded
{
    if (g[v].results[gr] != -1)
        return g[v].results[gr];

    if (v == 1)
        iG[v] = gr;

    LL x = 0;

    if (gr)
        x += g[v].cost;

    if (!gr)
    {
        for (auto i = g[v].neighbours.begin(); i != g[v].neighbours.end(); i++)
        {
            if (*i == a)
                continue;

            x += dfs(g, iG, *i, v, !gr);

            iG[v] = 1 - gr;
        }
    }
    else
    {
        for (auto i = g[v].neighbours.begin(); i != g[v].neighbours.end(); i++)
        {
            if (*i == a)
                continue;

            LL a = dfs(g, iG, *i, v, !gr);
            LL b = dfs(g, iG, *i, v, gr);

            if (a < b)
            {
                iG[v] = 1 - gr;
                x += a;
            }
            else
            {
                iG[v] = gr;
                x += b;
            }
        }
    }

    return g[v].results[gr] = x;
}

void output(vector<bool>& g, LL r, int size)
{
    cout << r << endl;

    for (int i = 1; i < size; i++)
        cout << g[i];

    cout << endl;
}

int main()
{
    int z;
    cin >> z;

    while (z--)
    {
        vector<vertex> graph;
        vector<bool> ifGuarded1, ifGuarded2;
        LL result1, result2;

        input(graph);

        ifGuarded1.assign(graph.size(), false);
        ifGuarded2.assign(graph.size(), false);

        result1 = dfs(graph, ifGuarded1, 1, 0, true);

        result2 = dfs(graph, ifGuarded2, 1, 0, false);

        if (result1 < result2)
            output(ifGuarded1, result1, graph.size());
        else
            output(ifGuarded2, result2, graph.size());
    }
}