I_Hate_Swaps's blog

Help needed for a tree problem
By I_Hate_Swaps, history, 2 years ago, In English

Given a Tree with n vertices(1 <= n <= 2e5) and all the vertices have some values assigned to them , we need to find the sum of xor of the paths between all the pairs of vertices. Can Anyone Please Help me in this problem..

If You can't help atleast don't downvote ^_^

  • Vote: I like it
  • -17
  • Vote: I do not like it

»
2 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

I will downvote because a similar problem is well-known and can be easily found on CodeChef. Moreover, all CodeChef submissions are public, and the very last of them has a clear solution that is easy to understand and adapt to our setting.

tl;dr: find the answer for each bit separately; for 0-1 weights the problem can be solved with a dfs that counts odd and even descending paths.

→ Reply