#P17851. [Ontak2019]GOT

[Ontak2019]GOT

— 哥谭谋杀案

哥谭市有 nn 个人,他们的日常联系关系构成一棵无向树。每个人最初是普通市民 C 或坏人 V。

一次操作中,选择两个仍然活着、且在原树中相邻的人 a,ba,b,让 aa 杀死 bb。死者从此消失;如果 aa 原来是普通市民,他会永久变为坏人。若本来就是坏人,身份不变。一次只能发生一起谋杀,不能让两个人同时互相杀死。

可以实施任意多次操作,也可以不实施操作。求最终存活的人中,坏人所占比例的最小值。树边表示原有联系,死亡不会让原来不相邻的人建立新联系。

输入格式

第一行一个整数 nn。第二行一个长度为 nn 的字符串,仅含 C 和 V,第 ii 个字符表示第 ii 个人最初的身份。

接下来 n−1n-1 行,每行两个整数 a,ba,b,表示树的一条边。

输出格式

输出两个互质整数 p,qp,q,以空格分隔,使 p/qp/q 等于最小坏人比例。比例为零时输出 0 1。

数据范围

1≤n≤1200001\le n\le120000,边的端点在 [1,n][1,n] 内,保证所给图是一棵树。

子任务 附加限制 分值
1 n≤20n\le20 10
2 n≤10000n\le10000 30
3 无 60

样例 1

输入:

4
CCVV
1 2
1 3
3 4

输出:

1 3

样例 2

输入:

4
CVCV
1 2
1 3
3 4

输出:

1 2