Tree and XOR
Contest: Mail.Ru Cup 2018 Round 2
Difficulty rating: 2900
Tags: strings, trees

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. $$$$$$

Input format:
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.

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

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

Note:
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$$$

Example input:
2 1
1 3

Example output:
0

Example input:
3 6
1 2
1 3

Example output:
2

Editorial:
First observation is that we may first assign a number to each vertex that is equal to xor of all values on the path from this vertex to the root (the root itself will be assigned $$$0$$$). Then the value of any path will be equal to xor of the values written in its first and last vertices.
Since the order of those values doesn't matter, let's build a binary trie of those numbers. In every node of the trie we will also store the number of values in its subtree. It's relatively easy to solve the reverse problem — to find number of paths having value not exceeding $$$v$$$. However the complexity of this is already $$$O(62 \cdot n)$$$, so adding binary search on top of it may not work. It's possible though to recover bits of the answer one by one by descending the trie level by level and maintaining the pairs of trie nodes that give us the correct higher bits of the answer (node may be in pair with itself).
At each step let's find the number of paths, whose next bit equals to $$$0$$$. In order to do this, we will go over the list of pairs. In every pair there may be two ways of obtaining $$$0$$$ as the next bit of the result: the corresponding bits of the values in the trie can be both zeros or both ones. In both cases we may compute number of paths as a product of the number of values in the corresponding subtrees. Then we sum all those numbers up over all the pairs. If the sum is greater or equal to $$$k$$$ then the next bit will be equal to $$$0$$$, otherwise it will be equal to $$$1$$$ (in this case we need to reduce $$$k$$$ by this number before proceeding to the next level). The amount of pairs at most doubles when we go one level deeper, but in total we will encounter the same node at most twice in the pairs.
The complexity of this algorithm is $$$O(62 \cdot n)$$$.
Since the full trie likely won't fit into memory, so we will build it implicitly — first sort the values first and then represent trie node with a range of indices on the sorted array. This will not change the overall complexity of the solution.