背景

题目来源：【HT-126-Div.2】核桃 CSP-S 组模拟赛

题目描述

给定一棵 $n$ 个节点的有根树，节点标号为 $1 \sim n$，根节点为 $1$。节点 $i$ 的权值为 $A_i$（保证 $A_i$ 互不相同）。给定一个常数 $X$。

对于树上的每一个节点 $u$，请你求出：在以 $u$ 为根的子树中，最多能选出多少个节点构成一个共鸣子集 $S$。

共鸣子集的定义为：对于集合 $S$ 中的任意两个不同节点 $x, y \in S$，都满足 $A_x \oplus A_y \ge X$。（其中 $\oplus$ 表示按位异或运算）

输入格式

第一行包含两个整数 $n, X$，分别表示树的节点数和给定的常数。

第二行包含 $n$ 个整数 $A_1, A_2, \ldots, A_n$，表示每个节点的权值。保证所有 $A_i$ 互不相同。

接下来 $n-1$ 行，每行两个整数 $u, v$，表示树上有一条连接节点 $u$ 和 $v$ 的边。

输出格式

输出一行一个整数，表示所有节点子树答案之和 $\sum_{i=1}^n ans_i$。

5 6
1 2 5 7 10
1 2
1 3
2 4
2 5

8

提示

【样例解释 #1】

对于子树 1，由于 $1 \oplus 7 = 6, 1 \oplus 10 = 11, 7 \oplus 10 = 13$，集合 $\{1, 7, 10\}$ 满足两两异或值 $\ge 6$。大小为 3，且无法选出大小为 4 的子集，故 $ans_1 = 3$。

对于子树 2，由于 $2 \oplus 10 = 8 \ge 6$，可选择集合 $\{2, 10\}$，故 $ans_2 = 2$。

对于子树 3、4、5，它们只有各自一个节点，故 $ans_3 = ans_4 = ans_5 = 1$。

答案之和为 $3 + 2 + 1 + 1 + 1 = 8$。

【数据范围】

本题采用捆绑测试。

对于 $100\%$ 的数据，$1 \le n \le 10^6$，$0 \le A_i, X < 2^{30}$。

*菊花图 指除了节点 $1$ 以外，所有节点均与节点 $1$ 直接相连。