PROBLEM LINK:
Authors: Praveen Dhinwa and Malvika Raj Joshi
Tester: Kevin Atienza
Translators: Vasya Antoniuk (Russian), Team VNOI (Vietnamese) and Hu Zecong (Mandarin)
Editorialist: Kevin Atienza
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:
- Given (u,v,x), the sum of the weights of all edges from u to v must have parity equal to x.
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^{K-1} \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^{N-1} assignments of weights to the N-1 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:
- The XOR of the weights of edges from u to w.
- The XOR of the weights of edges from v to w. (Note that the order doesnât matter because XOR is commutative and associative.)
We can modify this slightly. Since every number is its own XOR-inverse, 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:
- The XOR of the weights of edges from u to 1.
- The XOR of the weights of edges from v to 1.
This formulation counts the edge weights from w to 1 twice, which means they donât affect the XOR. (Every number is its own XOR-inverse, 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 one-to-one correspondence between edge weights and the variables x_1, x_2, \ldots, x_N. (Actually, only N-1 of these are actual âvariablesâ because x_1 is always 0.) This is straightforward:
- Any set of N-1 edge weights determines a unique assignment of the x_i variables.
- Similarly, any assignment of the variables x_2, \ldots, x_N determines unique edge weights for all edges: namely, the edge (i,j) gets the weight x_i \oplus x_j.
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^{N-1} 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 1
Each 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^{C-1}!
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 âodd-weight cycleâ in our graph. But finding such an odd-weight cycle is easy with a variant of graph bicoloring: No odd-weight cycle exists if and only if we can find a bicoloring of the graph such that:
- Every pair of nodes connected by an edge marked 0 have the same color, and
- Every pair of nodes connected by an edge marked 1 have different colors.
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):
- For each connected component, color one of its nodes red, and add it to a queue.
- Perform a BFS starting with our queue of nodes, and for each newly visited node, color it with either blue or red depending on the color of its parent and the mark of the edge.
- Check if this assignment is valid by checking if all edge conditions are satisfied.
So now we can summarize our algorithm:
- Ignore the given tree, and create a new graph with N nodes.
- For every condition (u,v,x), add an edge (u,v) marked x.
- Check if an âodd-weight cycleâ exists in the graph using the bicoloring algorithm above. If there is, then output 0.
- Otherwise, output 2^{C-1} \bmod (10^9 + 7), where C is the number of connected components.
The new graph contains N nodes and Q edges, so constructing it takes O(N+Q) time. Since checking for the existence of an odd-weight cycle only requires one traversal, it (and thus the whole algorithm) takes O(N+Q) time!
Solution 2
You can also use union-find 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:
- If x_a and x_b are friends, and x_b and x_c are friends, then x_a and x_c are friends.
- If x_a and x_b are enemies, and x_b and x_c are enemies, then x_a and x_c are friends.
- If x_a and x_b are friends, and x_b and x_c are enemies, then x_a and x_c are enemies.
To solve the problem, we will use union-find 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 union-find 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 union-find 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:
- If the representatives are the same, then x_u and x_v already belong to the same set, and nothing needs to be done.
- If the representatives point to each other as enemy sets, then we have reached a contradiction (because x_u and x_v are already known enemies), so we halt the process and immediately output 0.
- Otherwise, we call union on x_u and x_v. Also, we call union on the enemy sets of x_u and x_v. Note that we must also update the enemy pointers of the two new representatives.
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 representatives point to each other as enemy sets, then nothing needs to be done.
- If the representatives are the same, then we have reached a contradiction (because x_u and x_v are already known friends), so we halt the process and immediately output 0.
- Otherwise, we call union on x_u and the enemy set of x_v. Also, we call union on x_v and the enemy set of x_u. Note that we must also update the enemy pointers of the two new representatives.
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^{N-1} 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^{N-1-K} \bmod (10^9 + 7)!
Solution 3
There 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 union-find 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 union-find 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 the representatives are the same, then x_u and x_v already belong to the same set, so we only need to check if (u,v,x) is satisfied. This is true if and only if x = (D_u \oplus D_v). (Why?) So if this is false, we have reached a contradiction and can immediately output 0.
- Otherwise, the representatives are different, and we will need to perform a union operation. In this case, we will need to update the D_i value of the representative of either x_u or x_v. This new D_i must be equal to D_u \oplus D_v \oplus x. (Why?)
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^{C-1} \bmod (10^9 + 7)!
Time Complexity:
O(N + Q\alpha(N)) or O(N + Q)
(\alpha is the inverse Ackermann function)
