解题思路

1. 问题理解

• 有一棵 $n$ 个节点的树，每个节点颜色是 B（黑）或 R（红）。
• 路径上相邻两个节点颜色不同，则该路径是 颜色交错路径。
• 单节点路径也算颜色交错路径。
• 要求统计所有颜色交错的简单路径的条数。

2. 直接枚举不可行

• 树中路径数是 $\frac{n(n+1)}{2}$，如果直接枚举每条路径检查颜色，会是 $O(n^2)$，$n$ 最大 $2\times 10^5$ 时不可行。

3. 树形 DP 思路

考虑自底向上统计路径：

1. 初始化 每个节点至少有一条颜色交错路径（它自己），所以初始 pcnt[node] = 1。

2. 合并子树 对于节点 node 和它的子节点 nxt：

   • 如果 $color(node) \ne color(nxt)$：

     • 所有以 node 为起点的颜色交错路径，都可以和 nxt 子树中的颜色交错路径拼接形成新的颜色交错路径。

     • 拼接的条数是：

       $$\text{新增路径数} = pcnt[node] \times pcnt[nxt]$$

     • 然后把 pcnt[nxt] 加到 pcnt[node]，因为这些路径在合并后也可以往上层继续延伸。

3. 遍历顺序 为了保证子节点的统计值已经计算完成，需要自底向上遍历，这可以通过 BFS 定向化树后反向遍历实现。

时间复杂度：$O(n)$ ,空间复杂度：$O(n)$

Python 代码实现

from collections import deque

def read_input():
    """
    读取输入数据：
    - n：节点数量
    - graf：邻接表形式的树
    - stg：颜色字符串（'B' 或 'R'）
    """
    num = int(input())  # 节点数量
    graf = [[] for _ in range(num)]  # 邻接表
    # 读入 n-1 条无向边
    for _ in range(num - 1):
        u, v = map(int, input().split())
        u -= 1  # 转为 0-based 索引
        v -= 1
        graf[u].append(v)
        graf[v].append(u)
    # 节点颜色字符串
    stg = input().strip()
    return num, graf, stg


def build_back(graf):
    """
    使用 BFS 将树“定向化”（父 -> 子），并记录父子遍历顺序
    返回值 back 是一个列表，每个元素是 (父节点, 子节点)
    BFS 保证我们可以在反向遍历 back 时自底向上处理节点
    """
    deq = deque([0])      # 从根节点 0 开始 BFS
    back = [(-1, 0)]      # 根节点的父标记为 -1
    while deq:
        node = deq.popleft()
        # 遍历当前节点的邻居
        for nxt in list(graf[node]):
            graf[nxt].remove(node)   # 删除回到父节点的边，实现单向化
            deq.append(nxt)          # 子节点加入队列
            back.append((node, nxt)) # 记录父子关系
    return back


def solve(num, graf, stg):
    """
    主计算逻辑：
    - pcnt[i] 表示以 i 节点为起点向下延伸的颜色交错路径的数量（至少包含自己）
    - answ 记录总路径数，初始为 n（所有单节点路径）
    - 从叶子开始往上合并颜色交错路径
    """
    back = build_back(graf)  # BFS 得到父子遍历顺序
    pcnt = [1] * num         # 每个节点至少有 1 条路径（它自己）
    answ = num               # 单节点路径全部计入

    # 反向遍历 back，从叶子节点开始向上统计
    while back:
        prev, node = back.pop()  # 父节点 prev, 当前节点 node
        # 遍历当前节点的所有子节点
        for nxt in graf[node]:
            # 只有颜色不同的子树才能拼成颜色交错路径
            if stg[node] != stg[nxt]:
                # pcnt[node] 条路径 与 pcnt[nxt] 条路径 可以两两组合
                answ += pcnt[node] * pcnt[nxt]
                # 合并子树路径数到当前节点
                pcnt[node] += pcnt[nxt]
    return answ


def main():
    num, graf, stg = read_input()
    print(solve(num, graf, stg))


if __name__ == "__main__":
    main()

题目内容

小美有一棵由$n$个节点组成的树，每个节点被涂为红色或黑色。她想统计树中有多少条颜色交错的简单路径。

路径是指任意两个节点之间的唯一简单路径，并且我们也将单个节点自身视为长度为$1$的路径。若一条路径上任意相邻的两个节点颜色不同，则称该路径为颜色交错的路径。

请计算树中颜色交错的路径总数。

[名词解释]

树上的路径：从节点u到节点v的简单路径定义为从节点$u$出发，以节点$v$为终点，随意在树上走，不经过重复的点和边走出来的序列。可以证明，在树上，任意两个节点间有且仅有一条简单路径。

输入描述

第一行输入一个整数$n(1≦n≦2×105)$，表示树的节点数量。

接下来$n-1$行，每行输入两个整数$u$和$v (1≦u,v ≦n;u≠v)$，表示节点$u$与$v$之间有一条无向边。保证输入构成一棵树。

接下来一行，输入一个长度为$n$的字符串$s$，仅由字符$B$和$R$构成，其中$s_i=B$表示第$i$个节点为黑色;$s_i=R$表示红色。

输出描述

输出一个整数，表示树中颜色交错的路径总数。

样例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$条。