#P18141. Highway Hoax

Highway Hoax

Highway Hoax

You think this is something? You think this is bad? This? This chicanery?

——Chuck McGill, Better Call Saul

Albuquerque 是一座很大的城市。它有 nn 个路口和 n−1n-1 条有向公路。保证如果把所有公路都看成无向边,任意两个路口之间都可以互相到达(即这些边构成一棵树)。此外,每个路口有一个标签 S 或 F,分别表示起点(start)和终点(finish)。

Saul 和 Kim 准备再搞一次诡计。他们可以任意多次执行以下操作:

  • 选择一条公路 (u,v)(u,v),满足:
    • 这条公路的方向是从路口 uu 指向路口 vv;
    • 路口 uu 的标签是 S;
    • 路口 vv 的标签是 F。
  • 把这条公路的方向反转,并交换 uu 和 vv 上的标签。

请求出 Saul 和 Kim 通过任意多次操作能够得到的不同配置的数量。若两个配置中某个路口的标签不同,或某条公路的方向不同,就认为这两个配置不同。答案对 998244353998244353 取模。

输入格式

第一行一个整数 nn(2≤n≤2⋅1052\le n\le 2\cdot 10^5),表示路口数。

第二行一个长度为 nn 的字符串,只由 S 和 F 组成,第 ii 个字符表示第 ii 个路口初始的标签。

接下来 n−1n-1 行,每行两个整数 ui,viu_i,v_i(1≤ui,vi≤n1\le u_i,v_i\le n,ui≠viu_i\ne v_i),表示一条从 uiu_i 指向 viv_i 的公路。保证这些边构成一棵树。

输出格式

输出一个整数,表示可达的不同配置数对 998244353998244353 取模的结果。

样例 1

输入:

5
SFSFS
2 1
2 3
4 3
4 5

输出:

1

所有公路都是从 F 指向 S,无法执行任何操作。

样例 2

输入:

4
SFFF
1 2
1 3
1 4

输出:

4

对 v=2,3,4v=2,3,4 分别可以把 1→v1\to v 反转成 v→1v\to1,得到 3 个新配置,加上初始配置共 4 个。

样例 3

输入:

7
SSSSFFF
1 2
3 2
4 3
4 5
4 6
2 7

输出:

13