牛客网：题目链接： 感悟： 1.dfs的再理解，对树的遍历，用深度标记到根节点的距离。 2.树两点的最大距离的求解。

题意：

给定一棵无根树，树上每个节点被染成了红色或绿色或蓝色。（R=红色，G=绿色，B=蓝色） 一条边两个节点的颜色不同芭芭拉才能冲刺（即能形成一条边），问芭芭拉在这一颗树上能冲刺的最远距离 （不能重复经过一条边） 重点喔

思路：

实际是求树上两节点的最大距离，由于颜色相同的节点芭芭拉不能通过，就会使得树分割成多颗树， 保留根节点和子节点，用dfs遍历树的最大和次大深度，每次dfs之后，两深度之和的距离是以该根节点的最大距离，取其中距离最大的。 再解释一波 拿个图来解释一下吧： 1号节点， 那么经过他的最大距离是：顺序为一 1 五。 五：最大深度路线 。一：次大深度路线 1号节点。他的和为5+3=8；下面以次。 2号节点, 最大距离是：顺序为 一 2 二 3号节点 ， 最大距离是：顺序为三 3 五 4号节点， 最大距离是： 顺序为 四 4 五。 然后找出最大的距离。 可以发现在寻找一个节点时，先把它当成根，找以他为根起点的的最大深度路线和次大深度路线。 在分析一下吧，为什么要这么执行就一定可以得到树上两节点的最大距离。 要求到最大距离：那必然是从叶子节点出发到叶子节点结束。 (这里就不赘述了，多思考思考吧。假设不是叶子节点出发那会怎么样？？？，反之易得。。。)

题解代码如下：