阿里-淘天 0308笔试编程题-2 小红遍历树

题目描述：小红拿到了一棵树，树上的每个节点被染色成了红色、绿色或蓝色。

小红可以在两个不同颜色的相邻节点之间来回行走，但如果两个相邻节点的颜色相同，则不能行走。

小红可以在开始行走之前选择任意—个点修改它的颜色（最多只能修改一次），然后小红可以选择任意一个起始点开始行走。小红希望自己走过的节点数量尽可能多（一个节点走多次也只计算一次）。请你求出小红能走的最多节点数量。

输入描述：第一行输入一个正整数n，代表节点数量。

第二行输入一个长度为n的、仅由”R’、“G'、“B'三种字符组成的字符串，第i个字符为"R”代表1号节点被染成红色，G'代表染成绿色，“B'代表染成蓝色。

接下来的n-1行，每行输入两个正整数u和v，代表节点u和节点v有一条边连接。

1 ≤ n ≤ 100000

1 ≤ u,v ≤ n

输出描述：一个正整数，代表小红最多可以走的节点数量。

补充说明：

示例1

输入：5

RRRGB

12

13

14

15

输出：4

示例2

输入：3

RRB

12

23

输出：3

这道题是三道题中最难的一道，考察的是并查集，做出的同学寥寥无几，如过没有听说过并查集，可以尝试暴力方法，可以取得一部分的成绩。

并查集思路

理解“可移动”的条件：两个节点之间可以移动，前提是它们颜色不同。因此，树中所有颜色不同的相邻节点之间的边都是“可移动”的边。

在不进行任何颜色修改的情况下，树会被划分为若干个“可移动”连通分量。我们首先需要找到这些连通分量的大小，并记录最大的一个。

颜色修改的影响：通过改变一个节点的颜色，可以将其与原本颜色相同的相邻节点之间的边变为“可移动”边。这意味着通过改变颜色，可以将一些原本独立的连通分量合并成更大的连通分量。我们的目标是找出最佳的节点及其颜色修改，使得能够合并最多的连通分量，从而得到最大的连通分量。

综上：

1. 构建树的邻接表：根据输入的边信息，构建树的邻接表表示。
2. 使用并查集：遍历树的每条边，如果边两端的节点颜色不同，就将它们合并到同一个连通分量中。
3. 记录连通分量的大小：在并查集操作的同时，记录每个连通分量的大小。
4. 初始最大连通分量：遍历所有节点，找到当前最大的连通分量。
5. 对于每个节点，尝试将其颜色改为除当前颜色外的其他两种颜色中的一种。
6. 修改后的颜色可能会使该节点与更多的相邻节点颜色不同，从而连接更多的连通分量。
7. 对于每种可能的颜色修改，计算能够连接的连通分量的总大小，并记录最大的结果。
8. 比较不修改颜色时的最大连通分量和通过修改颜色得到的最大连通分量，取其中的更大值。

暴力思路

只需要抽出一个算法，计算染色后的最长路径，随后依次遍历所有节点，讲节点改为另外两种颜色分别抛下计算最长路径算法，最后取max即可。

计算染色后的最长路径 简单的DFS（注意将走过的节点放入Set中，防止因为环无法跳出循环）