#include<bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)
#define ll long long
#define vi vector <int>
#define sz(a) ((int) (a).size())
#define me(f, x) memset(f, x, sizeof(f))
#define uint unsigned int
#define ull unsigned long long 
#define i128 __int128
using namespace std;
const int N = 1 << 18;
int n, m;
vi e[N];

int siz[N], root, fn;
int vis[N];
void gsz(int x, int f) {
	siz[x] = 1;
	for(auto&v : e[x]) if(v != f && !vis[v]) {
		gsz(v, x);
		siz[x] += siz[v]; 
	}
}
inline void findrt(int x, int f) {
	int mx = 0;
	for(auto&v : e[x]) if(v != f && !vis[v]) {
		findrt(v, x);
		mx = max(mx, siz[v]);
	}
	mx = max(mx, fn - siz[x]);
	if(mx <= fn / 2) {
		root = x;
	}
}

namespace Hash {
const ll mod = (ll) 998244353 * 1019260817, base = 19491001;
ll Mul(ll a, ll b) {
	return (__int128) a * b % mod;
}
ll Add(ll a, ll b) {
	return (a + b) % mod;
}
ll Dec(ll a, ll b) {
	return (a + mod - b) % mod;
}
ll pw[N];
void init(int x) {	
	pw[0] = 1;
	L(i, 1, x) pw[i] = Mul(pw[i - 1], base);
}
}

struct oper {
	int op;
	int val;
	oper(int OP = 0, int VAL = 0) {
		op = OP;
		val = VAL;
	}
};

struct ds {
	int rev;
	char val[N];
	
	ll wn[N];
	int sz[N], beg[N];
	int mst[N];
	
	vi lstk, rstk;
	int ban, must, curv;
	vector < oper > ops;
	
	ll hsh[N];
	void clear(int x) {
		hsh[1] = 1919810;
		ops.clear();
		ban = 0;
		lstk.clear();
		rstk.clear();
		must = -1;
		curv = 0;
	} 
	
	void pop_r() {
		ops.emplace_back(oper(1, rstk.back()));
		rstk.pop_back();
	}
	
	void add_cur(int w) {
		ops.emplace_back(oper(2, w));
		curv += w;
	}
	
	void add_rsk(int w) {
		ops.emplace_back(oper(3, w));
		rstk.back() += w;
	}
	
	void pb_lsk(int w) {
		ops.emplace_back(oper(4, w));
		lstk.emplace_back(w);
		if(sz(lstk) > 1) {
			int n = sz(lstk);
			if(rev) {
			hsh[n] = Hash :: Add(hsh[n - 1], 
				Hash :: Mul(lstk[n - 1] - lstk[n - 2] + 114514, Hash :: pw[n]));	
			} else {
			hsh[n] = Hash :: Add(hsh[n - 1], 
				Hash :: Mul(lstk[n - 2] - lstk[n - 1] + 114514, Hash :: pw[n]));
			}
		}
	}
	
	void pb_ban(int w) {
		ops.emplace_back(oper(5, ban));
		ban = w;
	}
	
	void pb_must(int w) {
		ops.emplace_back(oper(6, must));
		must = w;
	}
	
	void pb_rsk(int w) {
		ops.emplace_back(oper(7, w));
		rstk.emplace_back(w);
	}
	
	void mark(int x) {
		if(ban) return ;
		if(val[x] == '|') {
			if(!sz(rstk)) {
				add_cur(1);
			} else {
				add_rsk(1);
			} 
		}
		
		if(val[x] == '}') {
			if(!sz(rstk)) {
				pb_lsk(curv);
				add_cur(-curv);
				return ;
			}
			int u = rstk.back();
			if(must != -1 && must != u) 
				pb_ban(1);
			pb_must(u);
			pop_r();
		} 
	
		if(val[x] == '{') {
			pb_rsk(0);
		} 
	}
	void make(int x) {
		if(!sz(rstk) && !curv && !ban) {
			mst[x] = must;
			sz[x] = sz(lstk);
			beg[x] = -1;
			if(sz[x]) {
				beg[x] = lstk[0];
			}
			wn[x] = hsh[sz[x]];
		} else {
			mst[x] = -2;
		}
	}
	void getv(int x, int f) {
		mst[x] = -2;
		int SZ = sz(ops);
		mark(x);
		make(x);
		for(auto&v : e[x]) if(v != f && !vis[v]) {
			getv(v, x);
		}
		while(sz(ops) > SZ) {
			auto tp = ops.back();
			if(tp.op == 1) {
				rstk.emplace_back(tp.val);
			} else if(tp.op == 2) {
				curv -= tp.val;
			} else if(tp.op == 3) {
				rstk.back() -= tp.val;
			} else if(tp.op == 4) {
				lstk.pop_back();
			} else if(tp.op == 5) {
				ban = tp.val;
			} else if(tp.op == 6) {
				must = tp.val;
			} else if(tp.op == 7) {
				rstk.pop_back();
			}
			ops.pop_back(); 
		}
	}
} d1, d2;
vi CUR;
void Getsiz(int x, int f) {
	CUR.emplace_back(x);
	for(auto&v : e[x]) if(v != f && !vis[v]) 
		Getsiz(v, x);
}

int sum[N];
vi roots[N];

ll ans[N];
namespace FFT {
	const double pi = acos(-1);
	struct CP {
		double x, y; 
		CP (double xx = 0, double yy = 0) {
			x = xx, y = yy;
		}
		inline CP rev() {
			return CP(x, -y);
		}
	} ;
	inline CP operator + (CP aa, CP bb) {
		return CP(aa.x + bb.x, aa.y + bb.y);
	}
	inline CP operator - (CP aa, CP bb) {
		return CP(aa.x - bb.x, aa.y - bb.y);
	}
	inline CP operator * (CP aa, CP bb) {
		return CP(aa.x * bb.x - aa.y * bb.y, aa.x * bb.y + aa.y * bb.x);
	}
	CP Pow[N], iPow[N];
	int Lim, pp[N], lim;
	void revlim() {
		L(i, 0, lim - 1) pp[i] = ((pp[i >> 1] >> 1) | ((i & 1) * (lim >> 1)));
	}
	void up(int x) {
		for(lim = 1; lim <= x; lim <<= 1) ;
	}
	void FFT(CP *f, int flag) {
		L(i, 0, lim - 1) if(pp[i] < i) swap(f[pp[i]], f[i]);
		for(int i = 2; i <= lim; i <<= 1) {
			for(int j = 0, l = (i >> 1), ch = Lim / i; j < lim; j += i) {
				for(int k = j, now = 0; k < j + l; k++) {
					CP pa = f[k], pb = f[k + l] * (flag == 1 ? Pow[now] : iPow[now]);
					f[k] = pa + pb, f[k + l] = pa - pb, now += ch;
				}
			}
		}
		if(flag == -1) L(i, 0, lim - 1) f[i].x /= lim, f[i].y /= lim;
	}
	void init() {
		Lim = 1 << 17;
		auto c = CP(cos(2 * pi / Lim), sin(2 * pi / Lim));
		auto tc = CP(cos(2 * pi / Lim), -sin(2 * pi / Lim));
		Pow[0] = iPow[0] = CP(1, 0); 
		L(i, 1, Lim) 
			Pow[i] = Pow[i - 1] * c;
		L(i, 1, Lim) 
			iPow[i] = iPow[i - 1] * tc;
	}
	CP ls[N], rs[N];
	void mul(int *a, int *b, int mxa, int mxb) {
		lim = 1;
		for(; lim <= mxa + mxb; lim *= 2); 
		revlim();
		L(i, 0, lim - 1) 
			ls[i] = rs[i] = CP(0, 0);
		L(i, 0, mxa) 
			ls[i] = CP(a[i], 0);
		L(i, 0, mxb) 
			rs[i] = CP(b[i], 0);
		FFT(ls, 1);
		FFT(rs, 1);
		L(i, 0, lim - 1) 
			ls[i] = ls[i] * rs[i];
		FFT(ls, -1);
		L(i, 0, mxa + mxb) 
			ans[i] += round(ls[i].x);
	}
}
int cnts[N];

int cl[N], cr[N];

int mul_l[N], mul_r[N];
void dc(int x) {
	gsz(x, 0), fn = siz[x], root = 0, findrt(x, 0);
	x = root, vis[x] = 1;
	
	priority_queue < pair < int, int > > q;
	sum[x] = 1, roots[x] = vi{x}, q.push({-sum[x], x}); 
	d1.clear(x), d2.clear(x);
	d1.mark(x), d1.make(x), d2.make(x);
	for(auto&v : e[x]) if(!vis[v]) {
		CUR.clear(), Getsiz(v, x), sum[v] = siz[v], roots[v] = CUR, q.push({-siz[v], v});
		d1.getv(v, x);
		d2.getv(v, x);
	}
	
	while(sz(q) > 1) {
		int u = q.top().second;
		q.pop();
		int v = q.top().second;
		q.pop();
		 
		L(cms, 0, 1) {
			
		vi Lp, Rp;
		for(auto&a : roots[u]) if(d1.mst[a] != -2) 
			Lp.emplace_back(a);
		for(auto&b : roots[v]) if(d2.mst[b] != -2)
			Rp.emplace_back(b);
		
		unordered_map < ll, pair < vi, vi > > mp;
		for(auto&a : Lp) 
			mp[d1.wn[a]].first.emplace_back(a);
		for(auto&b : Rp) 
			mp[d2.wn[b]].second.emplace_back(b);
			
		for(auto&s : mp) {
			vi l = s.second.first;
			vi r = s.second.second;
			if(!sz(l) || !sz(r))
				continue; 
			int have_size = d1.sz[l[0]];
			if(!have_size) {
				unordered_map < int, pair < int, int > > MP;
				ll gl = 0, gr = 0;
				for(auto&u : l) 
					if(d1.mst[u] != -1) 
						MP[d1.mst[u]].first += 1;
					else 
						++gl; 
				for(auto&u : r) 
					if(d2.mst[u] != -1) 
						MP[d2.mst[u]].second += 1;
					else 
						++gr;
				for(auto&s : MP) {
					ll hl = s.second.first;
					ll hr = s.second.second;
					ans[s.first] += hl * hr;
					ans[s.first] += hl * gr;
					ans[s.first] += gl * hr;
				}
				continue;
			}
			unordered_map < int, pair < vi, vi > > MP;
			vi tl, tr;
			for(auto&u : l) 
				if(d1.mst[u] != -1) 
					MP[d1.mst[u]].first.emplace_back(u);
				else tl.emplace_back(u);
			for(auto&v : r) 
				if(d2.mst[v] != -1) 
					MP[d2.mst[v]].second.emplace_back(v);
				else tr.emplace_back(v);
				
			for(auto&x : tl) 
				cl[d1.beg[x]] += 1;
			for(auto&x : tr) 
				cr[d2.beg[x]] += 1;
			for(auto&s : MP) {
				vi hl = s.second.first;
				vi hr = s.second.second;
				for(auto&r : hl) 
					cnts[d1.beg[r]] += 1;
				for(auto&r : hr) if(d2.beg[r] <= s.first)
					ans[s.first] += cnts[s.first - d2.beg[r]];
				for(auto&r : hl) 
					cnts[d1.beg[r]] -= 1; 
				
				for(auto&r : hl) if(d1.beg[r] <= s.first)
					ans[s.first] += cr[s.first - d1.beg[r]];
				for(auto&r : hr) if(d2.beg[r] <= s.first)
					ans[s.first] += cl[s.first - d2.beg[r]];
			}
			vector < pair < int, int > > ls, rs;
			for(auto&u : tl) {
				int x = d1.beg[u];
				if(cl[x]) 
					ls.emplace_back(x, cl[x]), cl[x] = 0;
			}
			for(auto&v : tr) {
				int x = d2.beg[v];
				if(cr[x]) 
					rs.emplace_back(x, cr[x]), cr[x] = 0;
			}
			sort(ls.begin(), ls.end());
			sort(rs.begin(), rs.end());
			int mxl = 0, mxr = 0;
			for(auto&u : ls) 
				mxl = max(mxl, u.first);
			for(auto&u : rs) 
				mxr = max(mxr, u.first);
			if((mxl + mxr) * log(mxl + mxr) <= (ll)sz(ls) * sz(rs)) {
				L(i, 0, mxl) 
					mul_l[i] = 0;
				L(i, 0, mxr) 
					mul_r[i] = 0;
				for(auto&u : ls) 
					mul_l[u.first] += u.second;
				for(auto&u : rs) 
					mul_r[u.first] += u.second;
				FFT :: mul(mul_l, mul_r, mxl, mxr);
			} else {
				for(auto&u : ls) 
					for(auto&v : rs) 
						ans[u.first + v.first] += (ll)u.second * v.second;
			}
		}
		
		swap(u, v);	
		}
		 
		for(auto&t : roots[v]) 
			roots[u].emplace_back(t);
		sum[u] += sum[v];
		q.push({-sum[u], u}); 
	}
	
	for(auto&v : e[x]) if(!vis[v]) 
		dc(v);
}

void dfs(int x, int p) {
	for(auto&v : e[x]) if(v != p) {
		dfs(v, x);
	}
}
int main () {
	Hash :: init(2e5);
	FFT :: init();
//	return system("fc matrix.out ex_matrix1.ans"), 0;
//	freopen("ex_matrix1.in", "r", stdin);
//	freopen("matrix.out", "w", stdout);
	ios :: sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n >> m;
	string S;
	cin >> S;
	L(i, 1, n) d1.val[i] = d2.val[i] = S[i - 1]; 
	L(i, 1, n) {
		if(d1.val[i] == '{') d1.val[i] = '}';
		else if(d1.val[i] == '}') d1.val[i] = '{';
	} 
	d2.rev = 1;
	L(t, 1, n - 1) {
		int u, v;
		cin >> u >> v;
		e[u].emplace_back(v);
		e[v].emplace_back(u);
	}
	dc(1);
	L(i, 0, m) cout << ans[i] << ' ';
	cout << '\n';
	return 0;
}