×

# XDCOMP - EDITORIAL

Setter: Daanish
Tester: Alexey Zayakin and Yash Chandnani
Editorialist: Taranpreet Singh

Medium

# PREREQUISITES:

Tree DP, Combinatorics and Observation.

# PROBLEM:

Given a tree with $N$ nodes, each node marked with a value $A[i]$ and a value $x$, Find out the number of ways to remove a subset of edges such that each of the new tree formed has xor-sum of all values in tree equal to x. Print this number of ways modulo $10^9+7$.

Let us call a subtree with xor-sum $x$ as special.

# QUICK EXPLANATION

• If the xor-sum of all nodes is not $x$ or $0$, it is not possible to achieve xor sum $x$ by removing any subset of edges. The number of ways being zero in this case.
• Now, If a node has subtree xor-sum $x$, it shall be divided into an odd number of special trees, removing an even number of edges. Alternatively, if xor-sum of the subtree of a node is zero, it shall be divided into even number of special trees, by removing an odd number of edges.
• For each node, we can calculate the number of ways to remove odd as well as even number of edges such that each of the generated trees is special. For now, ignore the fact that subtree xor of current node may differ from 0 or $x$.
• Number of ways to remove the number of edges from the subtree of a node is an XOR-convolution of the number of ways to remove edges from the subtree of each of its children.
• If subtree xor of a node (not being the root) is $x$, the number of ways to remove an odd number of edges become the sum of the number of ways to remove odd and even number of edges. Similarly, if the subtree xor-sum is $0$, the number of ways to remove even number of edges become the sum of the number of ways to remove odd and even number of edges.
• Corner case $x = 0$. Here, the number of ways is $2^x$ where $x$ is the number of nodes with subtree xor being zero excluding root, only if subtree xor of the whole tree is zero. Otherwise, there is no way to split given tree into special subtrees.

# EXPLANATION

First of all, Let's handle the base case, where $x = 0$. Here, Suppose we an edge connecting a subtree with xor-sum zero to its parent. The subtree xor is not affected at all. Hence, for every node (except root) which have subtree xor-sum zero, can be removed independently. If there are $x$ such nodes, considering each combination, there are a total of $2^x$ ways to remove edges.

Coming to general case, we can notice that $x \oplus y \oplus y = x$. This means, that if from the subtree of a node, we disconnect even number of special subtrees, the xor-sum of the tree is not affected. But if an odd number of special subtrees is disconnected, the xor-sum of remaining nodes in the subtree is XORed by $x$.

Let's denote $DPE_u$ denote the number of ways to remove even number of edges from subtree of node u and edge connecting u and its parent (except for root), while $DPO_u$ denote the number of ways to remove odd number of edges from subtree of node u plus the edge connecting node u and its parent. It's clear that initially, $DPE_x = 1$ (We have the DP state a bit unusual, but it eases implementation. It's possible to solve it normal way too).

Suppose a node x has two direct children, say u and v. It can be easily seen, that $DPE_x = DPE_u*DPE_v + DPO_u*DPO_v$ while $DPO_x = DPE_u*DPO_v+DPO_u*DPE_v$. Can you spot the pattern? It's basically the xor convolution. We can also visualize it as the polynomial multiplication, where each node is represented by a variable of degree 1, $x^i$ being the number of ways to remove $i$ edges.

Now comes the trouble. We have the option of removing the edge connected current node with its parent (assuming current node is not root). If we do not remove that edge, the number of ways is just the XOR convolution of the number of ways to remove edges for children of the current node.

Suppose we have subtree xor of current node as $x$. In this case, if we were removing even number of edges, we always have the choice to remove an odd number of edges by removing the edge connecting current node with its parent, thus removing an odd number of nodes for each way we can remove an even number of nodes. Thus, we increase $DPO_x$ by $DPE_x$ if the subtree xor of a node is $x$ and the node is not root.

Similarly, if the subtree xor of a node is $0$, and we have removed an odd number of edges, we have the choice to remove the edge connecting the current node to its parent resulting in removing an even number of edges. Hence, if subtree xor of the node is zero, we can remove an even number of edges for every way we were able to remove odd number of edges. Hence, we can simply increase $DPE_x$ by $DPO_x$ if the subtree xor of the node is $0$ and the node is not root.

Consider example tree where node 2, 3 and 6 are labeled 1, and rest are labeled zero. $x = 1$ for this example.

For node 6, $DPE_6 = 1$ as we may not remove edge 2-6. $DPO_6 = 1$ if we choose to remove edge 2-6.

For node 5, $DPE_5 = 1$ as we may not remove edge 2-5. $DPO_5 = 0$ as we cannot remove any odd number of edges, making special subtrees.

For node 4, $DPE_4 = 1$ as we may not remove edge 2-4. $DPO_4 = 0$ as we cannot remove any odd number of edges, making special subtrees.

For node 3, $DPE_6 = 1$ as we may not remove edge 1-3. $DPO_6 = 1$ if we choose to remove edge 1-3.

For node 2, we have to perform XOR convolution of number of ways of all its children, where $DPE$ is coefficient of $x^0$ and $DPO$ is coefficient of $x^1$. Clearly, we have $(1+1*x^1)*(1+0*x^1)*(1+0*x^1)$ which equates to $(1+x^1)$. This means, before considering edge 1-2, $DPE_2 = 1$ and $DPO_2 = 1$. Subtree xor of node 2 is 0, so, for every way to remove odd number of edges (excluding the edge connecting node and its parent), we can remove even number of edges if we choose to remove edge connecting node and its parent. So, we have $DPE_2 = DPE_2+DPO_2 = 2$ and $DPO_2 = 1$.

For node 1, we once again need to perform the same convolution. We have the product as $(1+1*x^1)*(2+1*x^1) = (2+3*x^1+1*x^2)$ Important thing here to notice is that coefficient of $x^2$ represent number of ways to remove 2 edges. We only care about parity here, so polynomial $(3+3*x^1)$ represent the same number of ways. Since this node is root, we cannot have any edge connecting this node to its parent.

Finally, xor-sum of the tree is 1, so, we can split this tree by removing an even number of edges, the answer to our problem is $DPE_0$, while if xor-sum is zero, the answer is $DPO_1$.

Those facing problem with this "convolution thing" refer the box below.

View Content

# Time Complexity

Time complexity is $O(N)$.

# AUTHOR'S AND TESTER'S SOLUTIONS:

Feel free to Share your approach, If it differs. Suggestions are always welcomed. :)

This question is marked "community wiki".

4.0k31104
accept rate: 22%

I intentionally included this "convolution thing".
I'm upvoting due to this "convolution thing". This was the first intuition which came to my mind. I used it. + Some stress tests to get AC. :P

(16 Feb, 16:54)

best solution i've found based on the editorial https://www.codechef.com/viewsolution/22866349

(22 Feb, 01:35) 4★

 4 I used similar approach, but can’t fully map it to the editorial description. I ended up deriving a formula for merging results from children’s nodes subtrees to a parent node. Not sure if those formulas just describe xor convolution approach. Here is the approach: Merge the original tree into a tree of nodes x and 0. Basically, starting from leaves, XOR a child node into a parent node if the child node is not x or zero. If x=0 then the answer is trivial power of two. Otherwise: For each node of the merged tree (all references to a tree below mean merged tree) let’s maintain two numbers {m,n}: n: number of ways to split the subtree of that node such that the node is in the connected group that XORs to x m: number of ways to split the subtree that the node is in the connected group that XORs to zero. Each leaf node that is equal to x gets {m,n} = {0,1} and each leaf node equal to zero gets {m,n} = {1,0}. For each node in a merged tree we can calculate {m,n} bases on the values for children nodes subtrees: Let’s calculate two numbers: A = Product of m[i] and B = Product of (2*n[i]+m[i]), where product is taken over all children nodes i. If the node is equal to x, then {m,n} = 1/2 * {B-A, B+A} If the node is equal to 0, then {m,n} = 1/2 * {B+A, B-A} The final answer is n of the root. https://www.codechef.com/viewsolution/22935893 answered 17 Feb, 12:27 6★shoom 353●4 accept rate: 30%
 3 Is there a tradition of codechef to never provide the link properly at first and fix it later. PS :- Sorry for being humouristic. Please fix the link. answered 18 Feb, 02:36 135●5 accept rate: 30%
 2 I don't get the convolution thing , can someone please explain that ? I am also gonna add my solution here since I think its much simpler : During the DFS , whenever the subtree xor becomes equal to X or 0 , remove the edge from that node to its parent. Shrink all the forests obtained to a node each and give it a value of 1 if xor was equal to X otherwise 0.Connect the removed edges again, the problem is reduced to finding the no. of partitions of the decomposed tree such that each each forest has an odd sum. This can be done using DP on children. $dp[i][0]$ = no. of ways to get even sum till the $i^{th}$ child. $dp[i][0] = dp[i-1][0]*(odd(c_i)+even(c_i)) + dp[i-1][1]*odd(c_i)$ (the odd case can be derived by swapping 1 for 0) where odd and even store the number of partitions such that the all parts that have been removed are odd and current is odd/even. answered 18 Feb, 20:03 120●5 accept rate: 0%
 1 For node 6, DPE6=1 as we may not remove edge 2-6. DPO6=1 if we choose to remove edge 5-6. There is no edge between 5-6. Finally, xor-sum of the tree is 1, so, we can split this tree by removing an even number of edges, the answer to our problem is DPE0, while if xor-sum is zero, the answer is DPO1. What is DPE0 here? Am i the only one who can't understand editorial of this problem even after reading many times and checking so many solutions. I don't understand how to use this convolution thing. answered 17 Feb, 18:52 5★vichitr 265●5 accept rate: 11% Point 1 was a typo, corrected. :) Which part u didn't understand? (17 Feb, 23:26)
 1 Basically for the convolution thing ,(a0*x0+a1*x1)*(b0x0+b1*x1)*(..)*(..)..... = (a0*b0*x0+(a0*b1+a1*b0)*x1)*(...)*(...)... and that makes sense as to make even edges ,(even+odd)*(even+odd)*... and finally take for even which is coefficient of x0.. answered 17 Feb, 20:49 21●2 accept rate: 0% 15.5k●1●20●66
 0 Can anyone explain how we arrived at this result :- "DPEx=DPEu∗DPEv+DPOu∗DPOv and DPOx=DPEu∗DPOv+DPOu∗DPEv." answered 02 Mar, 13:23 1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×2,657
×900
×264
×189
×115
×13