#include <bits/stdc++.h>    

using namespace std;

typedef long long ll;

const int N = (int)2e5 + 1, MOD = (int)1e9 + 7;

int n, dp[N][2], up[N][20], tin[N], tout[N], timer, b = 20, par[N], w[N], dep[N];
bool ok[N];
set<int> g[N];  
vector<pair<int, int>> e[N];

int root;
void build(int v, int pr) {
    tin[v] = ++timer;
    up[v][0] = pr;
    for(int i = 1; i < b; i++) {
        up[v][i] = up[up[v][i - 1]][i - 1];
    }
    for(int to:g[v]) {
        if(to != pr) {
            dep[to] = dep[v] + 1;
            build(to, v);
        }
    }
    tout[v] = ++timer;
}
bool is(int v, int u) {
    return  (tin[v] <= tin[u] && tout[u] <= tout[v]);
}
int lca(int v, int u) {
    if(is(v, u)) return v;
    if(is(u, v)) return u;
    for(int i = b - 1; i >= 0; i--) {
        if(!is(up[v][i], u)) {
            v = up[v][i];
        }
    }
    return up[v][0];
}
bool cmp(int x, int y) {
    return tin[x] < tin[y];
}
set<int> cur;
int p[N];
vector<int> er[N];
int get(int v) {
    if(p[v] == v) return v;
    int f = get(p[v]);
    return p[v] = f;
}
void make() {
    vector<int> t, t1;
    for(int i = 1; i <= n; i++) {
        if(ok[i]) {
            t.push_back(i);
        }
    }
    t1 = t;
    sort(t.begin(), t.end(), cmp);
    for(int i = 1; i < (int)t.size(); i++) {
        t1.push_back(lca(t[i], t[i - 1]));
    }
    sort(t1.begin(), t1.end());
    t1.resize(unique(t1.begin(), t1.end()) - t1.begin());
    sort(t1.begin(), t1.end(), cmp);
    vector<int> st;
    for(int i:t1) {
        cur.insert(i);
        p[i] = i;
        while(!st.empty() && !is(st.back(), i)) {
            st.pop_back();
        }
        if(!st.empty()) {
            e[st.back()].push_back({i, dep[i] - dep[st.back()] - 1});
            par[i] = st.back();
            w[i] = dep[i] - dep[st.back()] - 1;
        }
        st.push_back(i);
    }
}
void prec() {
    vector<int> u(n + 1), d(n + 1, 0);
    function<void(int)> go = [&](int v){
        d[v] = (ok[v] ? 0 : (int)1e9);
        for(auto [to, w] : e[v]) {
            go(to);
            d[v] = min(d[to] + w + 1, d[v]);
        }
    };
    function<void(int)> recalc = [&](int v) {
        multiset<int> vals;
        vals.insert(u[v]);
        for(auto [to, w] : e[v]) {
            vals.insert(d[to] + w);
        }
        for(auto [to, w] : e[v]) {
            if(ok[to]) {
                u[to] = 0;
                recalc(to);
            } else {
                vals.erase(vals.find(d[to] + w));
                u[to] = (*vals.begin()) + 1 + w;
                vals.insert(d[to] + w);
            }
        }
    };
    go(root);
    recalc(root);
    for(int i:cur) if(!ok[i]) {
        int mn = u[i] - 1, mn1 = (int)1e9;
        for(auto [to, f] : e[i]) {
            if(d[to] + f < mn) {
                mn1 = mn;
                mn = d[to] + f;
            } else if(d[to] + f < mn1) {
                mn1 = d[to] + f;
            }
        }
        if(mn == u[i] - 1 || mn1 == u[i] - 1) er[mn + mn1 + 1].push_back(i);
        else {
            assert(mn1 < u[i] - 1);
            er[u[i] + mn].push_back(i);
        }
    }
}

void remove(int i) {
    p[i] = par[i];
    cur.erase(i);
}
void solve(int v, int k) {
    dp[v][1] = 1 + k;
    for(auto [to, w] : e[v]) {
        solve(to, k);
        dp[v][0] += min(dp[to][0], dp[to][1]);
        dp[v][1] += min(dp[to][0], min(dp[to][1], dp[to][1] + w - k));
    }
    if(ok[v]) {
        dp[v][0] = (int)1e9;
    }
}
void test() {
    cin >> n;
    if(n > 5000) return;
    for(int i = 1; i <= n; i++) {
        char x;cin >> x;
        if(x == '1') {
            ok[i] = 1; 
            root = i;
        }
    }

    for(int i = 1; i <= n - 1; i++) {
        int u, v;
        cin >> u >> v;
        g[u].insert(v);
        g[v].insert(u);
    }
    // root = 6;
    build(root, root);
    make();
    prec();
    for(int i = 1; i <= n;  i++) {
        e[i].clear();
    }
    int col = 0;
    for(int k = 1; k <= n; k++) {
        vector<int> rr;
        // for(int j:er[k]) {
        //     remove(j);
        //     col += w[j] + 1;
        // }
        for(int f:cur) if(f != root) {
            int t = get(par[f]);
            if(ok[f] && ok[t] && w[f] <= k) {
                rr.push_back(f);
                col += w[f] + 1;
            }
        }
        for(int f : rr) {
            remove(f);
        }
        for(int f:cur) {        
            if(f == root) continue;   
            int t = get(par[f]);
            e[t].push_back({f, w[f]});
        }
        solve(root, k);
        cout << min(dp[root][0], dp[root][1]) + col << '\n';
        for(int f:cur) {
            e[f].clear();
            dp[f][0] = dp[f][1] = 0;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int t = 1;
    // cin >> t;
    
    while(t--)
        test();
}