游游的三色树

[编程题]游游的三色树

游游拿到了一棵树，其中每个节点被染成了红色（r）、绿色（g）或蓝色（b）。
游游想删掉一条边，使得剩下的两个连通块各恰好有三种颜色。
游游想知道，有多少合法的边可以删除？

注：树指不含重边和自环的无向连通图。

第一行输入一个正整数，代表树的节点数量。
第二行输入一个长度为的、仅包含'r'、'g'、'b'的字符串，第  个字符表示节点  的颜色。
接下来的 行，每行输入两个正整数和，代表点和点有一条无向边连接。

合法的边的数量。

示例1

输入

7
rgbrgbg
1 2
2 3
3 4
4 5
5 6
6 7


如上图，只有删掉3-4这条边满足剩下两个连通块都有3种颜色。

算法知识视频讲解

暂无题解

来自：2022年携程秋招第一批

难度：

3条回答 14收藏 984浏览

游游的三色树

扫一扫，把题目装进口袋