解题思路

$n\le 1000$，从每个起点沿树 DFS 不回头，维护当前二进制值。走过至少一条边后，若值落在 $[l,r]$ 中则计数。值已超过 $r$ 且为正时可以剪枝。

复杂度分析

时间复杂度 $O(n^2)$，空间复杂度 $O(n)$。

代码实现

题目内容

一棵 $n$ 个站点的通信树，每个站点标记为 0 或 1。沿一条至少包含一条边的路径，把沿途标记从起点到终点看成一个二进制数（起点为最高位）。需要统计有多少条有向路径，其数值落在闭区间 $[l,r]$ 内，用于评估链路编码覆盖范围。

单独一个站点不构成合法路径。

约束：$1 \le n \le 1000$，$1 \le l \le r \le 100000000000000$。

输入描述

第一行三个正整数 $n$ $l$ $r$。 第二行一个长度为 $n$ 的 01 串，第 $i$ 个字符是节点 $i$ 的权值。 接下来 $n-1$ 行，每行两个正整数 $u$ $v$ 表示树边。

输出描述

输出一个整数，表示合法有向路径的条数。

样例1

输入

3 1 10
101
1 2
2 3

输出

6

说明

按题意模拟计算得到。

样例2

输入

2 1 1
10
1 2

输出

1

说明

按题意模拟计算得到。

样例3

输入

4 3 8
1110
1 2
1 3
3 4

输出

9

说明

按题意模拟计算得到。