Statement

here is the problem : https://oj.uz/problem/view/COCI21_hiperkocka

Abridged Statement : you are given a tree T with n edges , you want to find a tiling using T on the hypercube Q_n.A hypercube with Q_i is defined as a tree such that node x and node y have an edge if and only if bitwise xor of them is a power of 2.

(please see the problem if you couldnt understood the abridged statement)

Editorial & Issue

editorial : https://hsin.hr/coci/archive/2021_2022/contest2_solutions.zip

As you can see in the editorial , it gives a construction which appearantly works but it doesnt provide a proof :/ I couldnt make sense on spesifically this paragraph :

"The rest of the trees can be placed as follows: for each x ∈ {0, . . . , 2n − 1} that has an even number of ones in binary, we take the hipercube nodes on which the first tree was placed and xor their labels with x. Notice that in such a way we obtain 2n−1 trees."

Any help and insight provided for the problem is welcomed!