Problem Background

The students of Class 3-E have won a trip to the Okinawa islands in the south. After Nagisa defeated Takaoka, they were invited by Koro-sensei to participate in a "Ghost Fear Test" event.

The event takes place in a dark cave. Akabane Karma is now standing at the entrance of the cave with Okuda Ayami. Suddenly, Karma thought of something...

Problem Description

Koro-sensei told them that the cave can be approximated as an out-tree with $n$ nodes. Due to the terrain, the edges between nodes have a direction, and all edges are directed the same way. The root of this tree is the node with an in-degree of $0$. Each node has a scare value, given by $a_i$.

Koro-sensei mentioned that there are many scary paths in this cave. A path between two nodes $u$ and $v$ is considered a scary path if it meets the following conditions:

• Node $v$ must be in the subtree of node $u$.
• The OR value of the scare values of all nodes on the path from $u$ to $v$ is $\geq k$.

Walking a scary path will receive a surprise gift from Koro-sensei. Koro-sensei has prepared the surprise gifts in advance, but Karma already knows that Koro-sensei has some sneaky intentions, not to mention the number of surprise gifts might be insufficient! Koro-sensei has promised that there will be as many surprise gifts as there are scary paths. Karma has found out the number of surprise gifts Koro-sensei has prepared through some magical means. Now, he wants to know how many scary paths there are, which is the minimum number of surprise gifts Koro-sensei needs to prepare. If there are not enough, he will expose Koro-sensei's intentions. Karma wants to take advantage of this situation to tease Koro-sensei. So he has obtained Koro-sensei's map in advance and wants to know how many scary paths are there in this graph?

Input Format

The first line contains two integers $n$ and $k$.

The second line contains $n$ integers, representing the scare values of each node.

The next $n-1$ lines each contain two integers $u$ and $v$, indicating that there is a directed edge from node $u$ to node $v$, node $v$ cannot reach node $u$.

Output Format

A single line containing an integer, representing the number of scary paths in the cave.

Sample Input and Output

Sample Input #1

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

Sample Output #1

2

Sample Input #2

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

Sample Output #2

16

Sample Input #3

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

Sample Output #3

16

Notes

Sample Explanation #1

Only two paths meet the conditions:

1. $3 \to 1 \to 2$, the OR value of the scare values of all nodes on this path is $6 \operatorname{or} 5 \operatorname{or} 9 = 15$.
2. $1 \to 2$, the OR value of the scare values of all nodes on this path is $5 \operatorname{or} 9 = 13$.

Data Range

This problem uses batched testing.

• Subtask 1 (10 points): $n \leq 5 \times 10^3$, $k \leq 10^5$.
• Subtask 2 (30 points): For any edge, $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$.

For $100\%$ of the data, $1 \leq n \leq 10^6$, $1 \leq k, a_i \leq 10^9$.

Hints

The test points in the fourth subtask have a memory limit of 256MB, while the test points in the other subtasks have a memory limit of 128MB.

见题面 Input 部分

见题面 Output 部分