#P17851. [Ontak2019]GOT
[Ontak2019]GOT
— 哥谭谋杀案
哥谭市有 个人,他们的日常联系关系构成一棵无向树。每个人最初是普通市民 C 或坏人 V。
一次操作中,选择两个仍然活着、且在原树中相邻的人 ,让 杀死 。死者从此消失;如果 原来是普通市民,他会永久变为坏人。若本来就是坏人,身份不变。一次只能发生一起谋杀,不能让两个人同时互相杀死。
可以实施任意多次操作,也可以不实施操作。求最终存活的人中,坏人所占比例的最小值。树边表示原有联系,死亡不会让原来不相邻的人建立新联系。
输入格式
第一行一个整数 。第二行一个长度为 的字符串,仅含 C 和 V,第 个字符表示第 个人最初的身份。
接下来 行,每行两个整数 ,表示树的一条边。
输出格式
输出两个互质整数 ,以空格分隔,使 等于最小坏人比例。比例为零时输出 0 1。
数据范围
,边的端点在 内,保证所给图是一棵树。
| 子任务 | 附加限制 | 分值 |
|---|---|---|
| 1 | 10 | |
| 2 | 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