#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 是一座很大的城市。它有 个路口和 条有向公路。保证如果把所有公路都看成无向边,任意两个路口之间都可以互相到达(即这些边构成一棵树)。此外,每个路口有一个标签 S 或 F,分别表示起点(start)和终点(finish)。
Saul 和 Kim 准备再搞一次诡计。他们可以任意多次执行以下操作:
- 选择一条公路 ,满足:
- 这条公路的方向是从路口 指向路口 ;
- 路口 的标签是
S; - 路口 的标签是
F。
- 把这条公路的方向反转,并交换 和 上的标签。
请求出 Saul 和 Kim 通过任意多次操作能够得到的不同配置的数量。若两个配置中某个路口的标签不同,或某条公路的方向不同,就认为这两个配置不同。答案对 取模。
输入格式
第一行一个整数 (),表示路口数。
第二行一个长度为 的字符串,只由 S 和 F 组成,第 个字符表示第 个路口初始的标签。
接下来 行,每行两个整数 (,),表示一条从 指向 的公路。保证这些边构成一棵树。
输出格式
输出一个整数,表示可达的不同配置数对 取模的结果。
样例 1
输入:
5
SFSFS
2 1
2 3
4 3
4 5
输出:
1
所有公路都是从 F 指向 S,无法执行任何操作。
样例 2
输入:
4
SFFF
1 2
1 3
1 4
输出:
4
对 分别可以把 反转成 ,得到 3 个新配置,加上初始配置共 4 个。
样例 3
输入:
7
SSSSFFF
1 2
3 2
4 3
4 5
4 6
2 7
输出:
13