/**
 * @author  chenxia25
 * @created 2023.10.17 09:42:58
 */
#include <bits/stdc++.h>

void ckmin(auto &x, const auto &y) { if (y < x) x = y; }
void ckmax(auto &x, const auto &y) { if (y > x) x = y; }

#define sz(x) int(x.size())

const int INF = 0x3f3f3f3f;
const int64_t INF64 = 0x3f3f3f3f3f3f3f3fLL;

template <class T>
struct y_combinator {
  T f;
  y_combinator(const T &_f) : f(_f) {}

  template <class ...Ts>
  auto operator()(Ts &&...args) const {
    return f(*this, std::forward<Ts>(args)...);
  }
};

template <class ...Ts>
struct recursion_t {
  std::tuple<Ts&&...> tp;
  recursion_t(Ts &&...args) : tp(std::forward<Ts>(args)...) {}

  template <class ...Us>
  auto operator()(Us &&...args) const {
    return recursion_t<Us...>(std::forward<Us>(args)...);
  }
};

template <class T, class ...Ts>
auto operator/(const T &f, const recursion_t<Ts...> &rec) {
  const auto &func = y_combinator<T>(f);
  if constexpr (sizeof...(Ts) == 0) return func;
  else return std::apply(func, rec.tp);
}

recursion_t recursion;

template <class T, T _mod>
struct modint {
  using type = T;
  static constexpr T mod = _mod;

  T x;

  modint() : x(0) {}
  template <class U>
  modint(const U &val) : x(norm(val)) {}
  operator T() { return x; }

  template <class U>
  static T norm(const U &x) {
    if (x >= 0) {
      if (x < mod) return x;
      else return x % mod;
    } else {
      if (x >= -mod) return x + mod;
      else return x % mod + mod;
    }
  }

  // to be modified
  modint inverse() const {
    T u, v, d = [&](const auto &exgcd, T a, T b, T &x, T &y) {
      if (!b) return x = 1, y = 0, a;
      int d = exgcd(b, a % b, y, x);
      return y -= a / b * x, d;
    } / recursion(x, mod, u, v);
    assert(d == 1);
    return u;
  }
};

#define mint modint<T, mod>

// addition
template <class T, T mod>
mint &operator+=(mint &x, const mint &y) {
  if constexpr (mod <= std::numeric_limits<T>::max() / 2) {
    if ((x.x += y.x) >= mod) x.x -= mod;
  } else {
    typename std::make_unsigned<T>::type res = x.x + y.x;
    if (res >= mod) res -= mod;
    x.x = res;
  }
  return x;
}
template <class T, T mod, class U>
mint &operator+=(mint &x, const U &y) { return x += mint(y); }
template <class T, T mod>
mint operator+(mint x, const mint &y) { return x += y; }
template <class T, T mod, class U>
mint operator+(const U &x, const mint &y) { return mint(x) + y; }
template <class T, T mod, class U>
mint operator+(const mint &x, const U &y) { return x + mint(y); }

// subtraction
template <class T, T mod>
mint &operator-=(mint &x, const mint &y) {
  if ((x.x -= y.x) < 0) x.x += mod;
  return x;
}
template <class T, T mod, class U>
mint &operator-=(mint &x, const U &y) { return x -= mint(y); }
template <class T, T mod>
mint operator-(mint x, const mint &y) { return x -= y; }
template <class T, T mod, class U>
mint operator-(const U &x, const mint &y) { return mint(x) - y; }
template <class T, T mod, class U>
mint operator-(const mint &x, const U &y) { return x - mint(y); }

// multiplication
template <class T, T mod>
mint &operator*=(mint &x, const mint &y) {
  using U = typename std::conditional<std::is_same<T, int>::value, int64_t, __int128>::type;
  x.x = mint::norm(U(x.x) * y.x);
  return x;
}
template <class T, T mod, class U>
mint &operator*=(mint &x, const U &y) { return x *= mint(y); }
template<class T, T mod>
mint operator*(mint x, const mint &y) { return x *= y; }
template <class T, T mod, class U>
mint operator*(const U &x, const mint &y) { return mint(x) * y; }
template <class T, T mod, class U>
mint operator*(const mint &x, const U &y) { return x * mint(y); }

// division
template <class T, T mod>
mint &operator/=(mint &x, const mint &y) {
  return x *= y.inverse();
}
template <class T, T mod, class U>
mint &operator/=(mint &x, const U &y) { return x /= mint(y); }
template<class T, T mod>
mint operator/(mint x, const mint &y) { return x /= y; }
template <class T, T mod, class U>
mint operator/(const U &x, const mint &y) { return mint(x) / y; }
template <class T, T mod, class U>
mint operator/(const mint &x, const U &y) { return x / mint(y); }

// quick power
template <class T, T mod, class U>
mint power(mint x, U e) {
  assert(e >= 0);
  mint res = 1;
  for (; e; e >>= 1, x *= x) if (e & 1) res *= x;
  return res;
}

// comparison
template <class T, T mod>
bool operator<(const mint &x, const mint &y) { return x.x < y.x; }
template <class T, T mod>
bool operator<=(const mint &x, const mint &y) { return x.x <= y.x; }
template <class T, T mod>
bool operator>(const mint &x, const mint &y) { return x.x > y.x; }
template <class T, T mod>
bool operator>=(const mint &x, const mint &y) { return x.x >= y.x; }

// input & output
template <class T, T mod, class U>
U &operator<<(U &stream, const mint &x) { return stream << x.x; }
template <class T, T mod, class U>
U &operator>>(U &stream, mint &x) { return stream >> x.x; }

#undef mint

struct hash_t {
  int n;
  std::vector<uint64_t> a;
  void build(int _n) {
    std::mt19937_64 rng(19171107);
    n = _n;
    a.resize(n);
    for (auto &x : a) x = rng();
  }
  uint64_t operator()(int x) {
    return a[x];
  }
} hash;

struct info {
  int must = -1;
  uint64_t diff = 0;
  int first = -1;
};

template <int mod, int g>
auto dft(auto a, int iv) {
  using mint = modint<int, mod>;
  int n = sz(a);
  std::vector p(n, 0);
  for(int i = 1; i < n; ++i) p[i] = p[i / 2] / 2 + i % 2 * n / 2;
  for(int i = 0; i < n; ++i) if(i < p[i]) std::swap(a[i], a[p[i]]);
  for(int i = 1; i < n; i *= 2) {
    mint o = power(mint(g), (mod - 1) / (2 * i));
    if (iv == -1) o = o.inverse();
    std::vector w(i, mint(1)); 
    for(int k = 1; k < i; ++k) w[k] = w[k - 1] * o;
    for(int j = 0; j < n; j += 2 * i) for(int k = 0; k < i; ++k) {
      mint x = a[j + k], y = w[k] * a[i + j + k];
      a[j + k] = x + y, a[i + j + k] = x - y;
    }
  }
  if(iv == -1) { 
    mint inv = mint(n).inverse();
    for(int i = 0; i < n; ++i) a[i] = a[i] * inv;
  }
  return a;
}

template <int mod, int g> 
auto mul(const auto &a, const auto &b) {
  using mint = modint<int, mod>;
  if (a.empty() || b.empty()) return std::vector<mint>();
  int n = sz(a), m = sz(b), s = n + m - 1 == 1 ? 1 : 1 << std::__lg(n + m - 2) + 1;
  std::vector<mint> A(a.begin(), a.end()), B(b.begin(), b.end());
  A.resize(s), B.resize(s);
  A = dft<mod, g>(A, 1), B = dft<mod, g>(B, 1);
  for (int i = 0; i < s; ++i) A[i] *= B[i];
  A = dft<mod, g>(A, -1);
  A.resize(n + m - 1);
  return A;
}

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);

  int n, m;
  std::cin >> n >> m;
  std::string a;
  std::cin >> a;
  std::vector adj(n, std::vector<int>());
  for (int i = 0; i < n - 1; ++i) {
    int x, y;
    std::cin >> x >> y;
    --x, --y;
    adj[x].push_back(y), adj[y].push_back(x);
  }

  hash.build(n);

  std::vector ans(n - 1, 0LL);

  std::vector vis(n, false);
  std::vector size(n, 0), max_size(n, 0);

  auto centroid = [&](auto &centroid, int x, int tot, int fa) -> int {
    size[x] = 1, max_size[x] = 0;

    int res = -1;
    for (int y : adj[x]) if (!vis[y] && y != fa) {
      int t = centroid(y, tot, x);
      if (res == -1 || max_size[t] < max_size[res]) res = t;
      size[x] += size[y];
      ckmax(max_size[x], size[y]);
    }

    ckmax(max_size[x], tot - size[x]);
    if (res == -1 || max_size[x] < max_size[res]) res = x;
    return res;
  } / recursion;

  [&](auto &solve, int root) -> void {
    vis[root] = true;

    static std::vector data(2, std::vector(n, info()));
    static std::vector belong(n, 0);
    std::vector<std::tuple<uint64_t, int, int>> all;
    static std::vector subtree(n, all);

    auto dfs = [&](auto &dfs, int type, int x, int fa) -> void {
      static std::vector<int> stack(1), rest;
      static uint64_t diff = 0;
      static int must = -1;

      if (type == 0) {
        if (x == root || fa == root) belong[x] = x;
        else belong[x] = belong[fa];
      }

      char ch = a[x];
      if (type == 1 && ch != '|') ch ^= '{' ^ '}';

      auto diff_copy = diff;
      auto must_copy = must;
      int stack_back = stack.back(), stack_size = sz(stack);
      if (ch == '{') {
        int cnt = stack.back();
        if (sz(stack) == 1) {
          stack[0] = 0;
          rest.push_back(cnt);
          diff += ((type == 0 ? 1 : -1) * (cnt - rest[0]) + n) * hash(sz(rest) - 1);
        } else {
          stack.pop_back();
          if (must != -1 && must != cnt) must = INF;
          else must = cnt;
        }
      } else if (ch == '|') {
        ++stack.back();
      } else {
        stack.push_back(0);
      }

      if (sz(stack) > 1 || stack[0] != 0 || must == INF) data[type][x] = {INF, 0, -1};
      else {
        data[type][x] = {must, diff, sz(rest) ? rest[0] : -1};
        all.push_back(std::make_tuple(diff, type, x));
        if (x != root) subtree[belong[x]].push_back(std::make_tuple(diff, type, x));
      }

      for (int y : adj[x]) if (!vis[y] && y != fa) {
        dfs(type, y, x);
      }

      diff = diff_copy, must = must_copy;
      if (ch == '{') {
        if (stack_size == 1) {
          stack[0] = stack_back;
          rest.pop_back();
        } else {
          stack.push_back(stack_back);
        }
      } else if (ch == '|') {
        --stack.back();
      } else {
        stack.pop_back();
      }
    } / recursion;

    for (int x : adj[root]) if (!vis[x]) subtree[x].clear();
    dfs(0, root, -1);
    data[1][root] = info();
    all.push_back(std::make_tuple(0ULL, 1, root));
    for (int x : adj[root]) if (!vis[x]) {
      dfs(1, x, root);
    }

    auto calc = [&](int coef, auto &order) {
      std::sort(order.begin(), order.end());
      std::vector first(sz(order), 0), must(sz(order), 0);
      for (int i = 0; i < sz(order); ++i) {
        auto [_, type, x] = order[i];
        first[i] = data[type][x].first;
        must[i] = data[type][x].must;
      }

      for (int l = 0, r; l < sz(order); l = r + 1) {
        r = l;
        while (r + 1 < sz(order) && std::get<0>(order[r + 1]) == std::get<0>(order[l])) ++r;
        int mid = l - 1;
        while (mid + 1 <= r && std::get<1>(order[mid + 1]) == 0) ++mid;

        if (std::get<0>(order[l]) == 0) {
          static std::vector cnt(n, 0);
          for (int i = l; i <= mid; ++i) ++cnt[must[i]];
          for (int i = mid + 1; i <= r; ++i) {
            if (must[i] != -1) ans[must[i]] += coef * cnt[must[i]];
            else {
              for (int j = l; j <= mid; ++j) ans[must[j]] += coef;
            }
          }
          for (int i = l; i <= mid; ++i) cnt[must[i]] = 0;
        } else {
          int maxl = 0, maxr = 0;
          static std::vector cntl(n, 0), cntr(n, 0);
          std::vector<int> vl, vr;
          for (int i = l; i <= mid; ++i) if (must[i] == -1) {
            if (!cntl[first[i]]) vl.push_back(first[i]);
            ++cntl[first[i]];
            ckmax(maxl, first[i] + 1);
          }
          for (int i = mid + 1; i <= r; ++i) if (must[i] == -1) {
            if (!cntr[first[i]]) vr.push_back(first[i]);
            ++cntr[first[i]];
            ckmax(maxr, first[i] + 1);
          }

          for (int i = l; i <= mid; ++i) if (must[i] != -1) {
            int want = must[i] - first[i];
            if (want >= 0) ans[must[i]] += coef * cntr[want];
          }
          for (int i = mid + 1; i <= r; ++i) if (must[i] != -1) {
            int want = must[i] - first[i];
            if (want >= 0) ans[must[i]] += coef * cntl[want];
          }
          static std::vector gather(n, std::vector<int>());
          std::vector<int> musts;
          for (int i = l; i <= r; ++i) if (must[i] != -1) {
            if (gather[must[i]].empty()) musts.push_back(must[i]);
            gather[must[i]].push_back(i);
          }
          for (int mustv : musts) {
            auto &v = gather[mustv];
            static std::vector cnt(n, 0);
            for (int i : v) {
              if (i <= mid) ++cnt[first[i]];
              else {
                int want = mustv - first[i];
                if (want >= 0) ans[mustv] += coef * cnt[want];
              }
            }
            for (int i : v) cnt[first[i]] = 0;
            v.clear();
          }

          if (std::get<0>(order[l]) == n * hash(0)) {
            std::vector cl(cntl.begin(), cntl.begin() + maxl), cr(cntr.begin(), cntr.begin() + maxr);

            static bool flag = false;
            if (!flag) {
              flag = true;
              auto res1 = mul<1004535809, 3>(cl, cr);
              auto res2 = mul<998244353, 3>(cl, cr);
              assert(sz(res1) == sz(res2));
              for (int i = 0; i < sz(res1); ++i) {
                int64_t res = res1[i];
                while (res % 998244353 != res2[i].x) res += 1004535809;
                ans[i] += coef * res;
              }
            } else {
              auto res = mul<1004535809, 3>(cl, cr);
              for (int i = 0; i < sz(res); ++i) ans[i] += coef * int64_t(res[i]);
            }
          } else {
            for (int il : vl) for (int ir : vr) {
              ans[il + ir] += (int64_t)coef * cntl[il] * cntr[ir];
            }
          }

          for (int i = l; i <= mid; ++i) cntl[first[i]] = 0;
          for (int i = mid + 1; i <= r; ++i) cntr[first[i]] = 0;
        }
      }
    };

    calc(1, all);
    for (int x : adj[root]) if (!vis[x]) calc(-1, subtree[x]);

    for (int x : adj[root]) if (!vis[x]) {
      solve(centroid(x, size[x], root));
    }
  } / recursion(centroid(0, n, -1));

  for (int i = 0; i <= m; ++i) {
    std::cout << ans[i] << " \n"[i == m];
  }

  return 0;
}