思路

默认以1为根节点进行$dfs$遍历。

$dp[i][0]$表示在以$i$为根节点的子树中，且与$i$的连边为蓝色所有路径中最长的。$dp[i][1]$表示以$i$为根节点的子树中，与$i$的连边为红色的所有路径中最长的。那从前面两个$dp$我们可以知道以$i$为根节点，且选择了节点$i$的最长路径肯定是$dp[i][0]+dp[i][1]$。那假如我们讨论了所有子树，那么最长路径也肯定知道了。

现在问题在于如何得到所有节点的$dp$值呢。我们发现假如我们知道了一个节点u的所有子节点$v$的$dp$值，那么$u$的$dp$值也就知道了。因为节点$u$的$dp[u][x]=max(dp[v][x\oplus 1]+1)$.所以我们需要先知道所有子节点的$dp$值，再用子节点的$dp$值去更新父节点。这个我们用$dfs$去处理。

代码

题目内容

米小游是一位研究者，他在研究网络传输时遇到了一个问题。

他拿到了一张通讯网络的拓扑结构图，其中每条通讯线路被染成了红色或者蓝色。

他想找到一条长度最长的通讯路径，使得路径上相邻的两条线路颜色不同。

输入描述

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

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

若为 $'R'$ 代表这条边是红色， $'B'$ 代表这条边是蓝色。

$1\le n \le 10^5$

$1\le u,v\le n$

保证输入的是一颗树。

输出描述

一个正整数，代表米小游可以选择的路径最大长度。

样例

输入

4
1 2 R
2 3 B
3 4 B

输出

2

样例解释

选择 $1-2-3$ 的路径即可。