I used a considerably different approach for this problem, similar to some of the comments. First I realised that whether an element(in chain instead of tree) is present in the answer or not depends solely on k and d(depth) of that element. Let n be the maximum depth of the chain. Then i observed that if all set(1) bits in d are 0 in k(or 1 in binary negation of k), the element is present in xor(answer), else absent. Let x denote the next power of 2 >=n. I then used self explanatory approach to calculate answer for negation of all possible k less than x in O(nlogn). Also, please confirm that this works for all corner cases.
Heres the link to my solution, Please upvote. AC in 0.15 seconds
https://www.codechef.com/viewsolution/15387157
i also saw same pattern but got TLE in last cases(C++)…
That xoring of nodes at same depth…really mind blowing. That was a pretty neat observation honestly!!!
@adecemberguy I don’t think using C++ was the cause of TLE, \mathcal{O}(N \log N) should comfortably clear the limit. Perhaps there is some part of your code taking greater time than you expect?
The pattern can have periodicity upto N (roughly) , so if one tries to derive pattern by brute force (i.e. keep on doing recursion, calculating d_1,d_2,d_3... until a repetition/original configuration is obtained) then the last 2 cases give TLE.
1 Like
@tarun_1407 - Are you sure you took required values as long in JAVA? I was getting WA in C++ because of int. Changed it to long long, got 40 points.
i used long, got WA, even tried with BigInteger which i knew was much more than required, but still WA.
@meooow I was trying something very similar. Even though your solution is obviously correct, I’m struggling to understand it completely. I understand the part that it has periodicity on powers of 2 that are >= chain length. I also understand that it’s convenient to add 0’s to the end to make it power of two, since it seems to be easier to explore what happens on powers of two. I’m not getting the part where you merge 2 halves. Can you please elaborate more?
I have updated my answer to explain the recursive part in greater detail, take a look 
Wow… that is some solution
Hey everybody
I’ve made a video in 2 parts for this problem.
Part 1: [Tutorial] Codechef SEPT17 - WEASELTX | Problem Solving Skills - Part 1 - YouTube(Weasel does XOR on Tree - Part 1)
Part 2: [Tutorial] Codechef SEPT17 - WEASELTX | Problem Solving Skills - Part 2 | Why I Love Math - YouTube(Weasel does XOR on Tree - Part 2)
Did you guys notice the amazing look alike of “Sierpinski Triangle” Fractal in this problem? See the part 2 especially as I have discussed about it there.
Yes 
The binomial coefficients modulo 2 is exactly the Sierpinski Triangle. The author used this term when describing his solution, however I didn’t.
Math is love <3
Tried to make a video editorial I’m really bad at this but please do tell me if it’s helpful