import sys import threading MOD = 998244353 def inv(x): return pow(x % MOD, MOD - 2, MOD) def set_stirling(n): res = [0, 1] for i in range(1, n): res.append(0) for j in range(i, -1, -1): res[j + 1] = res[j] for j in range(i + 1): res[j] = (res[j] - i * res[j + 1]) % MOD return res def integral_matrix(n): W = [[0] * n for _ in range(n)] # Stirling number -> matrix W Q = set_stirling(n) invk = [inv(k + 1) for k in range(n)] # coef[a][k] = a^(k+1) / (k+1) coef = [] for a in range(n): row = [0] * n pw = a % MOD for k in range(n): row[k] = pw * invk[k] % MOD pw = pw * a % MOD coef.append(row) for i in range(n): R = [0] * n R[n - 1] = Q[n] for k in range(n - 1, 0, -1): R[k - 1] = (Q[k] + i * R[k]) % MOD denom = 1 for j in range(n): if j != i: denom = denom * (i - j) % MOD c = inv(denom) R = [r * c % MOD for r in R] for a in range(n): ca = coef[a] W[a][i] = sum(R[k] * ca[k] for k in range(n)) % MOD return W def apply_mat(W, p): return [sum(wij * pj for wij, pj in zip(row, p)) % MOD for row in W] def solve(n, s, edges): # graph[v] = [(to, id)] A->B なら 2i, B->A なら 2i+1 graph = [[] for _ in range(n)] for i, (a, b) in enumerate(edges): graph[a].append((b, 2 * i + 1)) graph[b].append((a, 2 * i)) W = integral_matrix(n) WT = [[W[a][j] for a in range(n)] for j in range(n)] # WT[j][a] = W[a][j] F = [None] * (2 * n) G = [None] * (2 * n) H = [None] * (2 * n) D = [None] * (2 * n) def setF(id_, f): F[id_] = f to_is_A = id_ & 1 G[id_] = apply_mat(W, f) if to_is_A: H[id_] = G[id_] D[id_] = F[id_] else: g = G[id_] H[id_] = [(t - g[t]) % MOD for t in range(n)] D[id_] = [0] * n def process(now, ids, targets): T = len(targets) d = len(ids) out = [[0] * n for _ in range(T)] is_x = s[now] == 'x' Hs = [H[x] for x in ids] Ds = [D[x] for x in ids] rn = range(n) ones = [1] * n zeros = [0] * n for j in rn: Dj = [Ds[i][j] for i in range(d)] L = [] for i in range(d): h = Hs[i] c = 1 + h[j] L.append([(c - h[t]) % MOD for t in rn]) preP = [None] * (d + 1) preK = [None] * (d + 1) sufP = [None] * (d + 1) sufK = [None] * (d + 1) preP[0] = ones preK[0] = zeros sufP[d] = ones sufK[d] = zeros for i in range(d): Li = L[i] pp = preP[i] pk = preK[i] dj = Dj[i] preP[i + 1] = [pp[t] * Li[t] % MOD for t in rn] preK[i + 1] = [(pk[t] * Li[t] + dj * pp[t]) % MOD for t in rn] for i in range(d - 1, -1, -1): Li = L[i] sp = sufP[i + 1] sk = sufK[i + 1] dj = Dj[i] sufP[i] = [Li[t] * sp[t] % MOD for t in rn] sufK[i] = [(sk[t] * Li[t] + dj * sp[t]) % MOD for t in rn] wj = WT[j] for k in range(T): x = targets[k] if x < 0: P = preP[d] K = preK[d] else: pp = preP[x] pk = preK[x] sp = sufP[x + 1] sk = sufK[x + 1] P = [pp[a] * sp[a] % MOD for a in rn] K = [(pk[a] * sp[a] + sk[a] * pp[a]) % MOD for a in rn] o = out[k] if j == 0 and is_x: out[k] = [(o[a] + wj[a] * K[a] + P[a]) % MOD for a in rn] else: out[k] = [(o[a] + wj[a] * K[a]) % MOD for a in rn] return out def dfs_down(now, par): ids = [] peid = -1 for to, eid in graph[now]: if to == par: peid = eid ^ 1 continue dfs_down(to, now) ids.append(eid) if par != -1: setF(peid, process(now, ids, [-1])[0]) def dfs_up(now, par): ids = [] targets = [] outs = [] for to, eid in graph[now]: ids.append(eid) if to != par: targets.append(len(ids) - 1) outs.append(eid ^ 1) out = process(now, ids, targets) for k in range(len(targets)): setF(outs[k], out[k]) for to, _ in graph[now]: if to != par: dfs_up(to, now) dfs_down(0, -1) dfs_up(0, -1) ans = 0 if n >= 2: w1 = W[1] for i in range(n - 1): f0 = F[2 * i] f1 = F[2 * i + 1] for j in range(n): ans = (ans + w1[j] * (1 - f0[j]) * f1[j]) % MOD for i in range(1, n): ans = ans * i % MOD return ans def main(): data = sys.stdin.buffer.read().split() pos = 0 t = int(data[pos]); pos += 1 res = [] for _ in range(t): n = int(data[pos]); pos += 1 s = data[pos].decode(); pos += 1 edges = [] for _ in range(n - 1): a = int(data[pos]) - 1 b = int(data[pos + 1]) - 1 pos += 2 edges.append((a, b)) res.append(solve(n, s, edges)) print("\n".join(map(str, res))) sys.setrecursionlimit(1 << 20) threading.stack_size(1 << 27) th = threading.Thread(target=main) th.start() th.join()