题目背景

3 年 E 班的同学们赢得了去南方的冲绳小岛的机会，在渚打败了鹰冈之后，他们受杀老师的邀请参加“试胆大会”。

试胆大会在一个黑漆漆的洞窟里面进行。赤羽 業（Akabane Karma）现在和奧田 愛美站在洞窟的门口。突然，業想到了一个事情。。。

题目描述

杀老师告诉过他们，洞窟可以近似地看成 $n$ 个点的外向树，因为地形原因，所以一个点到另一个点的边是有方向的，且边的方向都是同向的。这棵树的树根为入度为 $0$ 的点。每个点都有一个惊吓值，给出每个点的惊吓值 $a_i$。

杀老师告诉他们，这个洞穴有很多惊吓路径。如果两个节点 $u,v$ 构成的路径是一条惊吓路径的话，满足以下条件：

• $v$ 一定在 $u$ 的子树中。

• $u, v$ 这条路径上的所有的点的惊吓值的或值 $\geq k$。

走过一条惊吓路径就会收到杀老师的惊喜大礼。杀老师已经提前准备好了惊喜大礼，但是業当然已经知道杀老师有一些下流的意图，更别说惊喜大礼的数量可能不够！杀老师已经承诺有多少条惊吓路径就有多少个惊喜大礼。業已经通过一些神奇的途径知道了杀老师准备的惊喜大礼的个数，现在他想知道有多少条惊吓路径，也就是杀老师最少需要准备惊喜大礼的个数。如果不够，他就会揭穿杀老师的意图。现在業当然想赚，好好捉弄一下杀老师。所以他作弊提前得到了杀老师的地图，想问这个图里面有多少条惊吓路径？

输入格式

第一行两个整数 $n,k$。

第二行 $n$ 个整数，表示每个点的惊吓值。

接下来 $n-1$ 行，每行有两个整数 $u,v$ 表示节点 $u,v$ 之间有一条有向边，节点 $u$ 可以到达节点 $v$，节点 $v$ 不可以到达节点 $u$。

输出格式

一行一个整数，表示这个洞穴的惊吓路径条数。

5 10
5 9 6 4 2
3 1
3 4
1 2
1 5

2

7 5
6 7 4 5 7 8 9
1 2
2 3
2 4
1 5
5 6
5 7

16

8 5
4 3 2 5 6 7 6 2
1 2
1 5
2 3
2 4
5 6
5 7
6 8

16

提示

样例解释 #1

只有两条路径满足条件：

1. $3\to 1\to 2$，这条路径的所有点的惊吓值的或值是 $6\operatorname{or}5\operatorname{or}9=15$。

2. $1 \to 2$，这条路径的所有点的惊吓值的或值是 $5\operatorname{or}9=13$。

---

数据范围

本题采用捆绑测试。

• Subtask 1（10 points）：$n \leq 5 \times 10^3$，$k \leq 10^5$。
• Subtask 2（30 points）：对于任意一条边，$v=u+1$，$n \leq 10^6$，$k,a_i \leq 10^9$。
• Subtask 3（20 points）：$n \leq 10^5$，$k,a_i \leq 10^9$。
• Subtask 4（40 points）：$n \leq 5 \times 10^5$，$k,a_i \leq 10^9$。

对于 $100\%$ 的数据，$1 \leq n \leq 10^6$，$1 \leq k,a_i \leq 10^9$。

---

提示

第四个子任务中的测试点空间 256MB，其余子任务中的测试点空间 128MB。