小美有一棵由 n 个节点组成的树，每个节点被涂为红色或黑色。她想统计树中有多少条颜色交错的简单路径。 路径是指任意两个节点之间的唯一简单路径，并且我们也将单个节点自身视为长度为 1 的路径。若一条路径上任意相邻的两个节点颜色不同，则称该路径为颜色交错的路径。 请计算树中颜色交错的路径总数。 【名词解释】 【树上的路径】从节点 u 到节点 v 的简单路径定义为从节点 u 出发，以节点 v 为终点，随意在树上走，不经过重复的点和边走出来的序列。可以证明，在树上，任意两个节点间有且仅有一条简单路径。
第一行输入一个整数 n(1 ≤ n ≤ 2×10^5) ，表示树的节点数量。 接下来 n-1 行，每行输入两个整数 u 和 v (1 ≤ u,v ≤ n;u ≠ v) ，表示节点 u 与 v 之间有一条无向边。保证输入构成一棵树。 接下来一行，输入一个长度为 n 的字符串 s ，仅由字符 B 和 R 构成，其中 s_i=B 表示第 i 个节点为黑色； s_i=R 表示红色。
输出一个整数，表示树中颜色交错的路径总数。
6 1 2 2 3 3 4 4 5 3 6 BRBRBB
16
3 1 2 2 3 BBB
3
考点：树 · 组合数学 · 并查集
数据规模 n ≤ 200000 ｜ 限制 1 秒 / 256MB ｜ 标准输入输出
推荐方向：树
树结构上的遍历（DFS 求子树信息 / BFS 求层序），多数树题是「后序遍历 + 回溯」。
思路框架（树 通法 · 非本题专属）
实现要点：递归深度可能到 1e5，注意递归爆栈；必要时改迭代或调整递归深度。
复杂度：时间 O(n) ｜ 空间 O(n)
该范式的通法易错点
对照本题
样例 1：输入 6 / 1 2 / 2 3 / 3 4 / 4 5 / 3 6 / BRBRBB → 输出 16
这棵树共有 16 条颜色交错的路径（包括 6 条单节点路径、4 条长度为 2 的路径、3 条长度为 3 的路径、2 条长度为 4 的路径、1 条长度为 5 的路径）。
样例 2：输入 3 / 1 2 / 2 3 / BBB → 输出 3
只有单节点路径满足颜色交错，共 3 条。
解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。
本题来源：2025年秋招-美团-算法策略端-第一批笔试。