游游的二进制树
题号：NC256067
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

游游拿到了一棵树，共有n个节点，每个节点都有一个权值：0或者1。这样，每条路径就代表了一个二进制数。
游游想知道，有多少条路径代表的二进制数在[l,r]区间范围内？
（请注意：路径长度至少为1，例如，节点3到节点3虽然有一个权值，但并不是合法路径！）

输入描述:

第一行输入三个正整数n,l,r，用空格隔开。
第二行输入一个长度为n的01串，第i个字符代表i号节点的权值。
接下来的n-1行，每行输入两个正整数u和v，代表u号节点和v号节点有一条边连接。
1\leq n \leq 10^3
1\leq u,v \leq n
1\leq l \leq r \leq 10^{14}

输出描述:

一个整数，代表合法的路径条数。
示例1

输入

复制 
4 4 5
1010
1 2
2 3
3 4

输出

复制 
3

说明

路径1-2-3代表的二进制数为5。
路径3-2-1代表的二进制数为5。
路径4-3-2-1代表的二进制数为5。
示例2

输入

复制 
3 1 2
100
1 2
1 3

输出

复制 
6

说明

任意合法路径均在区间[l,r]内。