春招模拟赛第七场|阿里巴巴|2023.04.12研发岗笔试
- Status
- Done
- Rule
- IOI
- Problem
- 3
- Start at
- 2023-4-18 19:00
- End at
- 2023-4-18 20:20
- Duration
- 1.3 hour(s)
- Host
- Partic.
- 74
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
曾经有一个叫做塔子哥的年轻人,他是一个热衷于研究二叉树的数学家。他认为,一棵树只有当它的红色节点数量大于蓝色节点数量时才是好树。他的定义引起了人们的热议,有些人同意他的定义,有些人则持不同意见。但无论怎样,这个定义还是被广泛地接受了。
有一天,塔子哥发现了一棵好树,但他觉得它不够完美。于是他开始思考,如果能够将这棵好树分成两个好树,那它就更加完美了。
经过一番研究,他发现只需要删除一条边,就可以将这棵树分成两个好树。他想知道有多少种删除边的方案,于是他向你求助。
第一行输入一个正整数 n ,代表节点的数量。
第二行输入一个长度为 n 的,仅包含 'R'
和 'B'
两种字符的字符串,第 i 个字符为 'R'
代表第 i 个节点被染成红色,'B'
代表被染成蓝色。
接下来的 n−1 行,每行输入两个正整数 u 和 v ,代表节点 u 和节点 v 有一条边连接。
1≤n≤105
一个整数,代表删边的方案数。
输入
5
RRBRB
1 2
2 3
1 4
4 5
输出
0
样例解释
无论删除哪条边,都会导致有一个子树不是好树。
扫码备注加群即可,期待您的到来~
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.