Mail.Ru Cup 2018 Round 2 |
---|
Finished |
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. $$$$$$
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 < 2^{62}$$$) — the ancestor of vertex $$$i + 1$$$ and the weight of the corresponding edge.
Print one integer: $$$k$$$-th smallest xor of a path in the tree.
2 1
1 3
0
3 6
1 2
1 3
2
The tree in the second sample test looks like this:
For such a tree in total $$$9$$$ paths exist:
Name |
---|