树上双字符连通块划分(We Need Both a and b)

题目描述

本题对应 AtCoder Typical 90 第 073 题：We Need Both a and b。

给定一棵包含 $n$ 个节点的树，节点编号为 $1 \sim n$。每个节点 $i$ 上写有一个字符 $c_i$，且 $c_i$ 只能是 a 或 b。

你可以选择删去树上的若干条边（也可以一条都不删）。删边后，整棵树会分裂成若干个连通块。

如果一种删边方案满足：每一个连通块中都至少包含一个写有 a 的节点和一个写有 b 的节点，则称该方案是合法的。

请你求出合法删边方案的数量，结果对 $10^9 + 7$ 取模。

输入格式

第一行包含一个正整数 $n$，表示树的节点数。

第二行包含 $n$ 个用空格隔开的字符 $c_1, c_2, \dots, c_n$（每个字符为 a 或 b）。

接下来 $n - 1$ 行，每行包含两个正整数 $u, v$，表示树上的一条边。

输出格式

输出一行一个整数，表示合法删边方案数对 $10^9 + 7$ 取模的结果。

样例输入 #1

3
a b b
1 2
1 3

样例输出 #1

1

样例输入 #2

4
a b a b
1 2
1 3
2 4

样例输出 #2

1

数据范围

对于 $100\%$ 的数据，$2 \le n \le 10^5$，$c_i \in \{\text{a}, \text{b}\}$。

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1700。

测试点分布

出处：原题链接