小美有一棵由
个节点组成的树,每个节点被涂为红色或黑色。她想统计树中有多少条
颜色交错
的简单路径。
路径
是指任意两个节点之间的唯一简单路径,并且我们也将单个节点自身视为长度为 1 的路径。若一条路径上任意相邻的两个节点颜色不同,则称该路径为颜色交错的路径。
请计算树中颜色交错的路径总数。
【名词解释】
【树上的路径】从节点
到节点
的
简单路径
定义为从节点
出发,以节点
为终点,随意在树上走,不经过重复的点和边走出来的序列。可以证明,在树上,任意两个节点间有且仅有一条简单路径。