#include <bits/stdc++.h>    

using namespace std;

typedef long long ll;

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

#define int ll
vector<int> g[N], f[N];
bool ok[N], blocked[N];
int n, r[N], s[N], up[N][20], dep[N], tin[N], tout[N], timer;

void build(int v, int pr) {
    up[v][0] = pr;
    for(int i = 1; i < b; i++) {
        up[v][i] = up[up[v][i - 1]][i - 1];
    }
    tin[v] = ++timer;
    for(int to:g[v]) {
        if(to != pr) {
            r[to] = v;
            dep[to] = dep[v] + 1;
            build(to, v);
        }
    }
    tout[v] = ++timer;
}
bool is(int v, int u) {
    return (tin[v] <= tin[u] && tout[v] >= tout[u]);
}
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];
}
int get(int v, int u) {
    return dep[v] + dep[u] - 2 * dep[lca(u, v)] - 1;
}
void dfs(int v, int pr = -1) {
    s[v] = 1;
    for(int to:g[v]) {
        if(to == pr || blocked[to]) continue;
        dfs(to, v);
        s[v] += s[to];
    }
}
int find(int v, int pr, int total) {
    for(int to:g[v]) {
        if(to != pr && !blocked[to] && s[to] > total / 2) {
            return find(to, v, total);
        }
    }
    return v;
}
void decompose(int v, int pr = 0) {
    dfs(v);
    v = find(v, -1, s[v]);
    blocked[v] = 1;
    r[v] = pr;
    for(int to:g[v]) {
        if(!blocked[to]) {
            decompose(to, v);
        }
    }
}
set<pair<int, int>> st[N];
set<array<int, 3>> all;
int dp[N], c, L[N];
array<int, 3> get(int v) {
    auto it = (st[v].begin());
    int x = (*it).second, u = 1 + (*it).first;
    it++;
    int y = (*it).second; 
    u += (*it).first;
    return {u, x, y};
}
void make(int v) {
    auto [val, i] = (*st[v].begin());
    st[v].erase(st[v].begin());
    while(!st[v].empty()) {
        auto [x, j] = (*st[v].begin());
        if(i == j) {
            st[v].erase(st[v].begin());
            continue;
        } else {
            break;
        }
    }
    st[v].insert({val, i});
}
void add(int v, int val) {
    int x = v;
    while(v) {
        if((int)st[v].size() >= 2) {
            all.erase(get(v));
        }
        st[v].insert({get(x, v), val});
        make(v);
        if((int)st[v].size() >= 2) {
            all.insert(get(v));
        }
        v = r[v];
    }
}
void er(int v, int val) {
    int x = v;
    while(v) {
        if((int)st[v].size() >= 2) {
            all.erase(get(v));
        }
        st[v].erase({get(v, x), val});
        if((int)st[v].size() >= 2) {
            all.insert(get(v));
        }
        v = r[v];
    }
}
vector<int> v;
void slow() {
    int lst = -1;
    c =0 ;
    for(int i = 1; i <= n; ++i) {
        if(ok[i]) {
            ok[i] = 1;
            c++;
            if(lst != -1) {
                v.push_back(i - lst - 1);
            }
            lst = i;
        }
    }
    dp[c] = c;
    sort(v.rbegin(), v.rend());
    for(int i = c - 1; i >= 1; i--) {
        dp[i] = dp[i + 1];
        dp[i] += v.back();
        v.pop_back();
    }
    for(int k = 1; k <= n; k++) {
        ll res = (ll)1e17;
        for(int j = 1; j <= c; j++) {
            res = min(res, j * 1ll * k + dp[j]);
        }
        cout << res << '\n';
    }
}
void test() {
    cin >> n;
    for(int i = 1; i <= n; ++i) {
        char x;cin >> x;
        L[i] = i;
        if(x == '1') {
            ok[i] = 1;
            c++;
        }
        f[i].push_back(i);
    }
    if(c == 1) {
        for(int i = 1; i <= n; i++) {
            cout << 1 + i << '\n';
        }
        return;
    }
    bool sti = 1;
    for(int i = 1; i <= n - 1; i++) {
        int u, v;
        cin >> u >> v;
        if(v != u + 1) {
            sti = 0;
        }
        g[u].push_back(v);
        g[v].push_back(u);
    }
    if(sti) {
        slow();
        return;
    }
    dep[1] = 1;
    build(1, 1);
    decompose(1);
    dp[c] = c;
    for(int i = 1; i <= n; i++) {
        if(ok[i]) {
            add(i, i);
        }
    }
    auto merge = [&](int x, int y) {
        if(x == y) {
            exit(-1);
        }
        if((int)f[x].size() > (int)f[y].size()) {
            swap(x, y);
        }
        int o = lca(L[x], L[y]);
        auto dd = [&](int l, int r) {
            while(l != r) {
                if(!ok[l]) {
                    ok[l] = 1;
                    add(l, y);
                }
                l = up[l][0];
            }
        };
        dd(L[x], o);
        dd(L[y], o);
        L[y] = o;
        for(int i:f[x]) {
            er(i, x);
            add(i, y);
            f[y].push_back(i);
        }
        f[x].clear();
    };
    for(int i = c -  1; i >= 1; i--) {
        dp[i] = dp[i + 1];
        array<int, 3> val = (*all.begin());
        merge(val[1], val[2]);
        dp[i] += val[0];
    }
    for(int i = 1; i <= c; i++) {
        if(dp[i] > n) {
            exit(-1);
        }
    }
    for(int k = 1; k <= n; k++) {
        ll res = (ll)1e18;
        for(int j = 1; j <= c; j++) {
            res = min(res, j * 1ll * k + dp[j]);
        }
        cout << res << '\n';
    }
}

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

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