版权声明

本题版权归 所有。

题目来源：https://www.luogu.com.cn/problem/P12669

本题题面有改动，数据系使用下发的数据生成器自造。

题目背景

公元前 278 年的今天，伟大的诗人屈原投汨罗江自尽，距今已有 2303 年。

有一颗江边的树想要纪念他，所以请你来对这棵树做一些装饰。

题目描述

有一个 $n$ 个点的树，点的编号从 $1$ 到 $n$，第 $i$ 个点的点权是 $a_i$。

定义一条边 $(i, j)$ 的重量为 $a_i \oplus a_j$，即两个端点边权的异或和。

你可以执行以下操作最多 $k$ 次：选定一个点 $u$，将 $u$ 点删除，并断开 $u$ 连接的所有边。

答案为经过上述操作之后，题目给定的树形成的森林的最小重量。

你需要对于 $k \in [0,lim]$ 都计算出这个答案。

输入格式

第一行两个以空格分开的整数，分别是 $n$ 和 $lim$。

第二行共 $n$ 个以空格分开的整数，代表 $a_1,a_2,\cdots,a_n$。

接下来 $n-1$ 行，每行两个以空格分开的整数 $u,v$，代表 $u,v$ 之间存在一条边。

输出格式

输出一行 $lim+1$ 个由空格隔开的整数，分别代表 $k=0,1,2,\cdots,lim$ 的答案。

样例

5 3
1 4 5 1 4
1 2
2 3
3 4
4 5

15 6 0 0

数据范围

对于 C++ 语言，答案可能会超过 long long 范围，请使用 128 位整型，或者其他高精度。

对于全部的数据：$0 \le lim \le n \le 2000$，$\forall i \in [1,n]$，$0 \le a_i \le 2^{63}-1$，详细数据范围见下表。