1000ms

Difficulty: 6

所属公司 : 美团

时间 :2025年8月9日-算法岗

算法与标签>动态规划

会员或题库专享

请先，开通会员或购买题库美团机考编程题库，可解锁完整内容。

购买美团机考编程题库开通会员

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（美团机考编程题库），可解锁完整内容。

购买题库开通会员

解题思路

1. 问题理解

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

题目内容

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

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

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