CF1055F.Tree and XOR

You are given a connected undirected graph without cycles (that is, a tree) of $n$ vertices, moreover, there is a non-negative integer written on every edge.

Consider all pairs of vertices $(v, u)$ (that is, there are exactly $n^2$ such pairs) and for each pair calculate the bitwise exclusive or (xor) of all integers on edges of the simple path between $v$ and $u$. If the path consists of one vertex only, then xor of all integers on edges of this path is equal to $0$.

Suppose we sorted the resulting $n^2$ values in non-decreasing order. You need to find the $k$-th of them.

The definition of xor is as follows.

Given two integers $x$ and $y$, consider their binary representations (possibly with leading zeros): $x_k \dots x_2 x_1 x_0$ and $y_k \dots y_2 y_1 y_0$ (where $k$ is any number so that all bits of $x$ and $y$ can be represented). Here, $x_i$ is the $i$-th bit of the number $x$ and $y_i$ is the $i$-th bit of the number $y$. Let $r = x \oplus y$ be the result of the xor operation of $x$ and $y$. Then $r$ is defined as $r_k \dots r_2 r_1 r_0$ where:

r\_i = \\left\\{ \\begin{aligned} 1, ~ \\text{if} ~ x\_i \\ne y\_i \\\\ 0, ~ \\text{if} ~ x\_i = y\_i \\end{aligned} \\right.

给你一棵包含 $n$ 个顶点的连通无向无环图（即一棵树），且每条边上都写有一个非负整数。

考虑所有顶点对 $(v, u)$（这样的顶点对恰好有 $n^2$ 个），并对每一对计算连接 $v$ 与 $u$ 的简单路径上所有边上的整数的按位异或（xor）值。若路径仅包含一个顶点（即 $v = u$），则该路径上无边，其异或值定义为 $0$。

假设我们将得到的 $n^2$ 个异或值按非递减顺序排序。你需要找出其中第 $k$ 小的值。

异或（xor）运算的定义如下：

给定两个整数 $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{若} ~ x\_i \\ne y\_i \\\\ 0, ~ \\text{若} ~ x\_i = y\_i \\end{aligned} \\right.

The first line contains two integers $n$ and $k$ ($2 \le n \le 10^6$, $1 \le k \le n^2$) — the number of vertices in the tree and the number of path in the list with non-decreasing order.

Each of the following $n - 1$ lines contains two integers $p_i$ and $w_i$ ($1 \le p_i \le i$, $0 \le w_i \lt 2^{62}$) — the ancestor of vertex $i + 1$ and the weight of the corresponding edge.

第一行包含两个整数 $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 \lt 2^{62}$）—— 分别表示顶点 $i + 1$ 的祖先及对应边的权重。

Print one integer: $k$-th smallest xor of a path in the tree.

输出一个整数：树中路径的异或值的第 $k$ 小值。

The tree in the second sample test looks like this:

For such a tree in total $9$ paths exist:

1. $1 \to 1$ of value $0$
2. $2 \to 2$ of value $0$
3. $3 \to 3$ of value $0$
4. $2 \to 3$ (goes through $1$) of value $1 = 2 \oplus 3$
5. $3 \to 2$ (goes through $1$) of value $1 = 2 \oplus 3$
6. $1 \to 2$ of value $2$
7. $2 \to 1$ of value $2$
8. $1 \to 3$ of value $3$
9. $3 \to 1$ of value $3$

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

对于这样一棵树，总共存在 $9$ 条路径：

1. $1 \to 1$，权值为 $0$
2. $2 \to 2$，权值为 $0$
3. $3 \to 3$，权值为 $0$
4. $2 \to 3$（经过节点 $1$），权值为 $1 = 2 \oplus 3$
5. $3 \to 2$（经过节点 $1$），权值为 $1 = 2 \oplus 3$
6. $1 \to 2$，权值为 $2$
7. $2 \to 1$，权值为 $2$
8. $1 \to 3$，权值为 $3$
9. $3 \to 1$，权值为 $3$