题目背景

エンパープル。

Please,Forgive me and "Purple"

まだ真ん中の私Empurple

题目描述

雪有一棵大小为 $n$ 的树。

雪定义一种树上的染色方案的权值：

设 $a$ 为其红色极大连通块的大小的平方的和。

设 $b$ 为其蓝色极大连通块的大小的平方的和。

这种染色方案的权值为 $ab$。

树上一些点已经被染上了红或蓝色，请将剩余点分别染成红或蓝色，求所有合法染色方案的权值和。

设待染色节点的个数为 $C$，则所有合法染色方案共有 $2^C$ 个。

答案可能很大，请对 $998244353$ 取模。

输入格式

第一行输入一个整数 $n$。

接下来有 $n-1$ 行，每行两个整数 $u_i,v_i$ 代表树上的一条边 $(u_i,v_i)$。

接下来有一行，一共 $n$ 个字符的字符串 $s$。

当 $s_i=\texttt{r}$，该点为红色。

当 $s_i=\texttt{b}$，该点为蓝色。

当 $s_i=\texttt{w}$，该点待染色。

输出格式

输出答案对 $998244353$ 取模后的结果即可。

6
1 2
1 3
1 4
2 5
2 6
rbwrbw

186

20
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
wwwwwwwwwwwwwwwwwwww

678428480

10
1 2
2 3
3 4
3 5
3 6
3 7
5 8
7 9
4 10
wbwwwrwrrw

8056

4
1 2
1 3
2 4
rbbr

4

5
1 2
1 3
2 4
3 5
wbwrw

100

7
1 2
1 3
2 4
2 5
3 6
3 7
wbwrwbr

294

提示

样例一解释：

测试点分布

编号	分值	$n$ 的范围	特殊性质
0	10	$n \le 10$
1		$n \le 40$	$s_i =\texttt{w}$
2		$n \le 300$
3		$n \le 5000$
4		$n \le 10^6$	$s_i \in \{\texttt{r},\texttt{b}\}$
5		$n \le 2\times 10^5$	$s_i \in \{\texttt{r},\texttt{w}\}$
6			$s_i =\texttt{w}$
7		$n \le 2\times 10^6$	$u_i=v_i-1$
8		$n \le 10^6$	$u_i=1$
9		$n \le 2\times 10^6$

对于所有数据：$1\le n \le 2\times 10^6,s_i \in \{\texttt{r},\texttt{w},\texttt{b}\},1\le u_i,v_i\le n$。保证输入的是一棵树。