E. 异或树 - EOJ Monthly 2021.10 Sponsored by TuSimple

仪表盘所有提交榜单题解

单点时限: 4.0 sec

内存限制: 1024 MB

Cuber QQ 有一棵 $n$ 个结点的有根树，树根是 $1$ 号节点，树上每个节点有一个点权 $a_{i}$ 。

对于树上的两个节点 $u, v (u \neq v)$ , 若他们为祖先后代关系，则会产生一个新的价值，而且价值是 $v a l u e_{(u, v)} = a_{v} \oplus a_{u}$ 。

现在 Cuber QQ 想知道树上前 $k$ 大的价值。

输入数据第一行包含两个整数 $n, k$ ( $2 \leq n \leq 5 \times 10^{5}, 1 \leq k \leq min (\sum_{v} d e p_{v} - 1, 5 \times 10^{5})$ ) 。

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

接下来 $n$ 行，第 $i$ 行代表 $i$ 号点的权值 $a_{i}$ ( $1 \leq a_{i} \leq 2^{31} - 1$ )。

输出包含 $k$ 行，表示前 $k$ 大的异或值，从大到小依次输出。

Input

Output

5
3

NaN

比赛状态发生变化，点 OK 刷新。

OK

EOJ Monthly 2021.10 Sponsored by TuSimple