PROBLEM LINK:Authors: Praveen Dhinwa and Malvika Raj Joshi DIFFICULTY:Medium PREREQUISITES:XOR, disjoint set union, graph traversal, bicoloring PROBLEM:You are given an $N$node tree, and you need to assign weights to the edges. The weight of each edge can be $0$ or $1$, but they must satisfy $Q$ conditions of the following kind:
How many assignments of edge weights are there, modulo $10^9 + 7$? QUICK EXPLANATION:Root the tree on any node (say $1$), and for every node $i$, let $x_i$ be the XOR of all edge weights from root to $i$. Then the condition $(u,v,x)$ is satisfied if and only if $x_u \oplus x_v = x$, so we only need to count the assignments of the $x_i$s. Create a new graph with $N$ nodes, and add an edge from $u$ to $v$ with weight $x$ for every condition $(u,v,x)$. If this graph contains a cycle with odd total weight (which can be found with bicoloring), the answer is $0$. Otherwise, if this graph contains $K$ components, then the answer is $2^{K1} \bmod (10^9 + 7)$. EXPLANATION:In this explanation, we will go straight into the solution for the final subtask, and simply note that the first subtask can be solved by trying all $2^{N1}$ assignments of weights to the $N1$ edges (which runs in $O(N^2 2^N)$ time). First, the conditions seem quite complicated because each condition gives a restriction among weights of edges along some path, so potentially a lot of edges are affected per condition. As with any problem involving unrooted trees, it usually helps to root the tree first. Since we don't know any better yet, let's try rooting the tree at an arbitrary node, say at node $1$. When the tree is rooted, we can view a path as consisting of two parts, an upward path and a downward path. (One or both parts may consist of zero edges.) Specifically, consider the path from $u$ to $v$. Let $w$ be the lowest common ancestor of $u$ and $v$. Then the path from $u$ to $v$ consists of the path from $u$ to $w$ (the upward path) and the path from $w$ to $v$ (the downward path). The XOR of the weights of the edges from $u$ to $v$ is simply the XOR of the following two values:
We can modify this slightly. Since every number is its own XORinverse, we can also say that the XOR of the weights of the edges from $u$ to $v$ is the XOR of the following two values:
This formulation counts the edge weights from $w$ to $1$ twice, which means they don't affect the XOR. (Every number is its own XORinverse, which means these weights will cancel out in the XOR.) This gives us a possible alternative interpretation of the conditions: Define $N$ new variables $x_1, x_2, x_3, \ldots, x_N$, one for every node. Define $x_i$ to be the XOR of the edge weights from $i$ to $1$. Then the condition $(u,v,x)$ is satisfied if and only if $x_u \oplus x_v = x$. (Here $\oplus$ denotes the XOR operation.) This simplifies our conditions down to a simple relationship between two variables, $x_u$ and $x_v$! So our strategy now is to instead count the number of assignments of the $x_i$s. But for this strategy to work, we need to show that there is a onetoone correspondence between edge weights and the variables $x_1, x_2, \ldots, x_N$. (Actually, only $N1$ of these are actual "variables" because $x_1$ is always $0$.) This is straightforward:
Thus, we have reduced the problem to finding the number of assignments of the variables $x_2, \ldots, x_N$ satisfying $x_u \oplus x_v = x$ for all $(u,v,x)$. In addition to being, this interpretation has another benefit: Notice that we don't actually need the tree! (In other words, the tree doesn't matter in the final answer; only the conditions.) The most straightforward way of solving this new problem is still to try all $2^{N1}$ possible assignments, so our goal now is to solve it more efficiently. In the following, we will describe a few such solutions (all of which are related to one another). Solution 1Each condition $(u,v,x)$ gives a relationship between the two variables $x_u$ and $x_v$. Our first observation is that $x$ can only be $0$ and $1$. If $x = 0$, then the statement $x_u \oplus x_v = x$ is equivalent to the statement $x_u = x_v$, and if $x = 1$, then it is equivalent to $x_u \not= x_v$. Suppose first that $x = 0$ for all conditions. Then each condition $(u,v,x)$ says that the variables $x_u$ and $x_v$ are equal. Let's keep track of all these relationships with a new graph with $N$ nodes, where node $i$ corresponds to variable $x_i$. We add an edge $(u,v)$ for every condition $(u,v,x)$. In this graph, every two adjacent variables must be the same. This implies that all variables that belong to a connected component must be the same. Thus, in each connected component, there are only two possible assignments for all variables (because they must all be equal), except the component containing $1$ which only has one possible assignment (because $x_1$ must be $0$). So if there are $C$ connected components, then the number of assignments of variables is simply $2^{C1}$! Now, what if we include conditions with $x = 1$? In this case, we can still create a similar graph as above, but now we should mark each edge $(u,v)$ with $0$ or $1$, depending on the value of $x$. In this case, if an edge is marked $0$, then the variables it joins must be the same, otherwise they must be different. But again, in a connected component, selecting the value of some variable already uniquely determines the value of all other variables. (The difference is that this time, they are not necessarily all the same.) So we could also say that there are two possible assignments for each connected component (except the component containing $x_1$). But this is not true, because it may happen that the conditions are unsatisfiable! For example, suppose we have the conditions $(10,20,1)$, $(20,30,1)$ and $(30,10,1)$. Then the nodes $x_{10}$, $x_{20}$ and $x_{30}$ belong to a connected component, but any assignment to these variables will not satisfy all conditions simultaneously! (Because we cannot find values $x_{10}$, $x_{20}$ and $x_{30}$ satisfying $x_{10} \not= x_{20}$, $x_{20} \not= x_{30}$ and $x_{30} \not= x_{10}$.) Such a thing happens because we found an "oddweight cycle" in our graph. But finding such an oddweight cycle is easy with a variant of graph bicoloring: No oddweight cycle exists if and only if we can find a bicoloring of the graph such that:
But finding such a coloring is easy and can be done with the following (assuming we're trying to color the nodes either red or blue):
So now we can summarize our algorithm:
The new graph contains $N$ nodes and $Q$ edges, so constructing it takes $O(N+Q)$ time. Since checking for the existence of an oddweight cycle only requires one traversal, it (and thus the whole algorithm) takes $O(N+Q)$ time! Solution 2You can also use unionfind instead of bicoloring. This has a slightly lower complexity, but might be easier to code. This solution is inspired by this problem. Each condition says that $x_u$ and $x_v$ are either equal or not equal. Let's introduce some new terms. Let's say that $x_u$ and $x_v$ are friends if they have the same value, and enemies if they have different values. The following are intuitive facts about friendship and enemyship:
To solve the problem, we will use unionfind on our $N$ variables $x_1, \ldots, x_N$, and our goal is to partition these variables so that if we know two variables $x_i$ and $x_j$ are friends, then they must belong on the same set. Initially, each variable is in their own set. Furthermore, we will modify unionfind so that each disjoint set $S$ of variables knows its enemy set $T$, which we'll define as the set of variables which are enemies of the variables in $S$. To implement this, just add a pointer for each node called enemy, and point this pointer from the representative of $S$ to the representative of $T$, and vice versa. Initially, each set doesn't have an enemy set. (Or you can add dummy enemy sets by adding $N$ new variables, which could be simpler to implement.) Now, we will handle the conditions $(u,v,x)$ in order, and update our unionfind along the way. First, let's handle a condition $(u,v,x)$ with $x = 0$. In this case, $x_u$ and $x_v$ are friends so we want $x_u$ and $x_v$ to belong to the same set. The first step is to find the representatives of the sets containing $x_u$ and $x_v$. Then we handle a few cases:
Handling a condition $(u,v,x)$ with $x = 1$ is similar. In this case, $x_u$ and $x_v$ are enemies so we want $x_u$ and $x_v$ to belong to a pair of sets which are enemy sets of each other. As before, the first step is to find the representatives of the sets containing $x_u$ and $x_v$. Then we handle a few cases:
If the overall process succeeds without arriving at a contradiction, then we know that the conditions are satisfiable. The remaining question is how many possible assignments are there. Well, this is easy. Before we processed any condition, there were $2^{N1}$ possible assignments. However, for every condition that gave us new information (i.e. those that made us perform union operations), we essentially entangled the fates of two sets of variables, thus reducing the number of possibilities by $2$. Thus, if there are $K$ conditions that forced us to do unions, then the answer is simply $2^{N1K} \bmod (10^9 + 7)$! Solution 3There is another solution that involves union find but is slightly different from the previous solution. Instead of placing friends in one set and their enemies in another, we place all known friends and enemies in a single set, thus removing the need for the enemy pointer. But in this version, we must remember the relationships of variables in the same set with each other. Specifically, for each node $i$, we will keep track of a bit called $D_i$, which is $1$ if $x_i$ is an enemy of its parent in the disjoint set forest, and $0$ otherwise. For simplicity, if $i$ is the representative of the set, then we say the parent of $i$ is itself, so $D_i = 0$. As we perform unionfind operations, we will need to update this $D_i$. For example, during a union operation, we need to update the $D_i$ of one of the nodes. Also, during a find operation, we will perform path compression and update the $D_i$s of all nodes in the path along the way. Note that path compression will be required in this solution. As before, we will process the conditions $(u,v,x)$ in order and update our unionfind as we go. But unlike before, the cases $x = 0$ and $x = 1$ don't need to be handled separately. The first step is to find the representatives of $x_u$ and $x_v$. Then we will handle the following cases:
If we are able to process all $Q$ conditions without arriving at a contradiction, then all that remains is to count how many possible assignments there are. But this is similar to the first solution: If there are $C$ distinct sets, then the answer is simply $2^{C1} \bmod (10^9 + 7)$! Time Complexity:$O(N + Q\alpha(N))$ or $O(N + Q)$ ($\alpha$ is the inverse Ackermann function) AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 13 Mar '16, 14:25

Is it really that easy, that it is given tag "Easy" ? answered 15 Mar '16, 15:11

A very nice editorial to a "tough seeming" problem. answered 24 Mar '16, 01:29

I Did it in a very different ways i applied dfs in conditions and checked if the loops were satisfiable and counted no. of edges which were fixing values of edges i mean every condition fixed value of one edge if it wasn't completing a loop and lastly got the answer (2^left no. of edges) answered 15 Mar '16, 20:52

Please explain with an example. It is very difficult to understand. answered 15 Mar '16, 21:50

I also did the same thing but did not get accepted ? Was your solution accepted ? My answer passed on 10 test cases out of 19 . answered 17 Mar '16, 15:04

Can anyone explain this line: Any set of N−1 edge weights determines a unique assignment of the xi variables answered 15 Dec '17, 17:57

"However, for every condition that gave us new information (i.e. those that made us perform union operations), we essentially entangled the fates of two sets of variables, thus reducing the number of possibilities by 2". I cannot understand it. (Weak mathematical background) :( answered 29 Jan, 22:54
