0
$\begingroup$

I tried two approaches:
1. Give each edge two numbers on its left and right side denoting xor sum for subtree on its left and right respectively. If total xor sum for whole tree is Z, then it can only be partitioned into odd groups each with xor sum Z. I observed some partition patterns with particular edges as follows.
let edge be denoted by (a--b) where a and b are numbers on its left and right. Then partitions are in the form P1(x--0)P2(0--x)P3 and then recursively check for P1,P2,P3. Similarly if total xor sum is 0, partitions are in the form P1(x--x)P2. But there seems to be analytical formula for this pattern which i cant find.

2.Tree Parent Child relationship: consider a root node and its xor sum for the subtree rooted at this node. Corresponding to this xor sum value, we can partition its child nodes and try to make a formula in terms of no of children and no of ways to partition them recursively but again the expression i get is a mess.

There has to be a good approach please help.

$\endgroup$
  • $\begingroup$ It's not clear to me (a) whether values are stored only in the leaves or also in internal nodes; (b) whether the partition only deletes edges or whether it allows e.g. a node to be split into two or more nodes which partition its children. $\endgroup$ – Peter Taylor Feb 12 at 14:28
  • $\begingroup$ @PeterTaylor, a) values are stored in all nodes(root,internal,leaves) b) only edges can be deleted $\endgroup$ – iro otaku Feb 12 at 14:39
  • $\begingroup$ Please add a reference to the original source of the problem in the question. $\endgroup$ – Apass.Jack Feb 12 at 22:02

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.