小塔有一颗有n个节点的树,其中每个节点是红色或者黑色,她想知道,删除一个红色节点以及与它相连的全部边后,剩余连通快↓中黑色节点数量的最大值是多少。
↓:对于树上的两个点,如果它们相互连通,则称他们位于同一个连通快里;显然,在执行删除操作后,剩余部分至多构成两个连通块。
第一行输入一个整数 n(1≤n≤105)代表节点的数量。
第二行输入一个长度为n的字符串s1s2......sn(si∈{'R''B'})代表第i个节点的颜色为si。若si为‘B’表示节点的颜色为黑色,若si为‘R’则表示节点的颜色为红色。保证s中至少有一个红色节点。
此后n−1行,第i行输入两个整数ui和vi(1≤ui,vi≤n;ui=vi)表示树上第i条边连接节点ui和vi。
在一行上输出一个整数代表最大值
输入
10
RRBBBBBBBB
1 2
1 3
1 4
1 5
1 7
2 8
4 6
4 10
6 9
输出
7
扫码备注加群即可,期待您的到来~
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.