题目描述

这是问题的简单版本。在这个版本中 $n \le 1000$。

给定一棵 $n$ 个节点的树，每个节点都有一个权值（$0$ 或 $1$）。

任意一条路径上的节点权值依次组成一个二进制数。定义路径长度至少为 $1$（即至少包含两个节点）。

请统计有多少条路径对应的二进制数在区间 $[L,R]$ 内。

输入格式

• 第一行输入三个正整数 $n, L, R$。
• 第二行输入一个长度为 $n$ 的 01 串，第 $i$ 个字符表示第 $i$ 个节点的权值。
• 接下来 $n-1$ 行，每行两个正整数 $u,v$，表示节点 $u$ 和 $v$ 之间有一条边。

输出格式

输出一个整数，表示符合条件的路径数量。

4 4 5
1010
1 2
2 3
3 4

3

解释 #1

在样例中：

• 路径 $1\to2\to3$ 对应二进制数 $101_2=5$。
• 路径 $3\to2\to1$ 对应二进制数 $101_2=5$。
• 路径 $4\to3\to2\to1$ 对应二进制数 $0101_2=5$。 共 $3$ 条路径满足条件。

数据范围

• $1 \leq n \leq 1000$
• $1 \leq u,v \leq n$
• $1 \leq L \leq R \leq 10^{14}$