← 返回题目列表

Codeforces · 1055/F

F. 树和异或

中文机器翻译题面 查看原题

给你一个由 $$$n$$$ 个顶点组成的无环无向连通图(即一棵树),而且每条边上都写有一个非负整数。

考虑所有顶点对 $$$(v, u)$$$ (即,恰好存在 $$$n^2$$$ 这样的对),并为每对计算 $$$v$$$ 和 $$$u$$$ 之间简单路径边缘上的所有整数的按位异或 (xor)。如果路径仅由一个顶点组成,则该路径边上的所有整数的异或等于 $$$0$$$。

假设我们按非降序对生成的 $$$n^2$$$ 值进行排序。您需要找到其中的第 $$$k$$$。

异或的定义如下。

给定两个整数 $$$x$$$ 和 $$$y$$$,考虑它们的二进制表示形式(可能带有前导零): $$$x_k \dots x_2 x_1 x_0$$$ 和 $$$y_k \dots y_2 y_1 y_0$$$ (其中 $$$k$$$ 是任意数字,以便 $$$x$$$ 和$$$y$$$ 可以表示)。这里,$$$x_i$$$是数字$$$x$$$的第$$$i$$$位,$$$y_i$$$是数字$$$y$$$的第$$$i$$$位。设 $$$r = x \oplus y$$$ 为 $$$x$$$ 和 $$$y$$$ 异或运算的结果。然后 $$$r$$$ 定义为 $$$r_k \dots r_2 r_1 r_0$$$ 其中:

$$$$$$ r_i = \left\{ \begin{aligned} 1, ~ \text{if} ~ x_i \ne y_i \\ 0, ~ \text{if} ~ x_i = y_i \end{aligned} \right。 $$$$$$

输入

第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \le n \le 10^6$$$, $$$1 \le k \le n^2$$$) - 树中的顶点数和列表中的非递减顺序的路径数。

以下 $$$n - 1$$$ 行中的每一行都包含两个整数 $$$p_i$$$ 和 $$$w_i$$$ ($$$1 \le p_i \le i$$$, $$$0 \le w_i < 2^{62}$$$) - 顶点 $$$i + 1$$$ 的祖先和相应边的权重。

输出

打印一个整数:$$$k$$$ - 树中路径的第一个最小异或。

示例

输入 #1

2 1
1 3

输出 #1

0

输入 #2

3 6
1 2
1 3

输出 #2

2

注意

第二个示例测试中的树如下所示:

对于这样一棵树,总共存在 $$$9$$$ 路径:

1. $$$1 \ 至 1$$$ 价值 $$$0$$$
2. $$$2 \ 至 2$$$ 价值 $$$0$$$
3. $$$3 \ 至 3$$$ 价值 $$$0$$$
4. $$$2 \to 3$$$ (经过 $$$1$$$)价值 $$$1 = 2 \oplus 3$$$
5. $$$3 \to 2$$$ (经过 $$$1$$$)价值 $$$1 = 2 \oplus 3$$$
6. $$$1 \ 至 2$$$ 价值 $$$2$$$
7. $$$2 \ 至 1$$$ 价值 $$$2$$$
8. $$$1 \ 至 3$$$ 价值 $$$3$$$
9. $$$3 \ 至价值 $$$3$$$ 的 1$$$