P17758 「RSOI-3G」树上操作 / tree

题目来源：【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$。

**【样例解释 #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}$。 | Subtask | 分值 | $n \le$ | 特殊性质 | | :---: | :---: | :---: | :---: | | 1 | $5$ | $15$ | 无 | | 2 | $10$ | $10^3$ | 无 | | 3 | $5$ | $10^6$ | $X = 0$ | | 4 | $10$ | $10^6$ | 树的形态为以 $1$ 为中心的菊花图* | | 5 | $15$ | $10^6$ | 树的形态为一条单链 | | 6 | $25$ | $10^5$ | 无 | | 7 | $30$ | $10^6$ | 无 | ***菊花图** 指除了节点 $1$ 以外，所有节点均与节点 $1$ 直接相连。