题目描述

小红拿到了一棵二叉树，每个节点的权值为0或1。

小红希望从根节点出发，每次前往左儿子或者右儿子，直到走到叶子时停止，路径上所有节点将表示为一个二进制数（按路径顺序)。小红希望最终的二进制数在区间[l, r]内，请你告诉小红有多少种不同方案。

输入描述

输入包含n + 2行，第一行输入一个整数n，表示二叉树的节点数量；

第二行输入n个整数，表示每个节点的权值ai；

后续n - 1行，每行输入两个整数u, v，表示编号为u，v节点连接了一条边。

最后一行输入两个整数，表示l, r.

1 <= n < = 105;

0 <= ai <= 1;

1 <= u, v <= n;

1 <= l <= r <= 109.

题目保证根节点的编号为1。

输出描述

输出一个整数表示答案。

输入示例

4
1 0 1 1
1 2
1 3
2 4
2 3

输出示例

1

提示信息

选择路径1 -> 3，得到的二进制数字是11，表示十进制的3，在[2, 3]范围内。即一条路径满足题目所述条件。

时间限制：c/c++：1s；其他语言：4s。