This blog is coauthored by gohchingjayk.
Hello Codeforces!
In this blog, we will first introduce this property, and then use it to improve the solution to 2260F - Edge Three-Coloring! =D
What is the property?
Theorem 1. Suppose we have a set $$$S$$$ which is a subset of the vertices on a rooted tree. Now, let $$$T = \lbrace \operatorname{LCA}(u, v) \mid u, v \in S \rbrace$$$. We claim that $$$|T \setminus S| \le |S| - 1$$$.
Proof. Consider the Eulerian Tour of the tree. Let $$$pre_u$$$ be the first visit of node $$$u$$$ in the Eulerian Tour. It is known that $$$\operatorname{LCA}(u, v)$$$ is the node of the minimum depth between $$$pre_u$$$ and $$$pre_v$$$ (inclusive).
Now, consider 2 nodes, $$$u, v \in S$$$. Suppose there exists node $$$x$$$ such that $$$pre_u \lt pre_x \lt pre_v$$$. Observe that the node of minimum depth between $$$pre_u$$$ and $$$pre_v$$$ is either $$$\operatorname{LCA}(u, x)$$$ or $$$\operatorname{LCA}(x, v)$$$.
There are exactly $$$|S| - 1$$$ pairs $$$u, v \in S$$$ where there exists no $$$x \in S$$$ such that $$$pre_u \lt pre_x \lt pre_v$$$. Thus, $$$|T \setminus S| \le |S| - 1$$$. $$$\square$$$
Taking a look at 2260F - Edge Three-Coloring
If you haven't solved this problem before, I recommend taking a look first. Otherwise, here is a short summary of the solution.
The solution takes advantage of property 6 in this blog — that cycles in a graph form a linear space using symmetric difference. Now, take an arbitrary spanning tree of the graph. Each of the $$$C = M - (N - 1)$$$ edges (call them "special") outside this spanning tree forms a unique cycle together with the tree path between its endpoints. We show that these $$$C$$$ cycles form a basis of this linear space.
Firstly, let's show that these $$$C$$$ cycles span the linear space. Recall that in a tree, there exists exactly one simple path between any 2 nodes. Thus, at least one of these $$$C$$$ edges must be used in order to create a cycle.
Next, let's show that these $$$C$$$ cycles are linearly independent. Note that as each cycle uses a different edge external to the spanning tree, it cannot be created as a linear combination of the other cycles.
Now, the solution to the problem is as follows:
Bruteforce all $$$2^C$$$ (non-empty) subsets of cycles in the basis. Now, for a subset, we find the symmetric difference of all the cycles in it, and check if the remaining edges form a connected graph.
The final complexity of the solution is $$$O(2^C \cdot (N + M) \cdot\alpha(N))$$$.
Can we do better?
Here, "original tree" refers to the arbritrary spanning tree chosen in the earlier part.
Let $$$S$$$ be the set of all endpoints of the $$$C$$$ "special" edges. We can define $$$T$$$ similarly to above, and let $$$S'=S\cup T$$$. It is easy to see that $$$|S'|\le 2\cdot C-1$$$. For any vertex of the tree not in $$$S'$$$, if we root the tree at that vertex, there exists at most two child subtrees which contain vertices in $$$S'$$$.
Now, consider the symmetric difference of subsets of cycles in the bases. Consider vertices $$$u,v\in S'$$$ such that there does not exist a vertex $$$x$$$ on the simple path between $$$u,v$$$ which is also contained in $$$S'$$$. We assert that in the symmetric difference of any subset of cycles, if any edge on the simple path from $$$u$$$ to $$$v$$$ is included, then all edges on the path are included.
Suppose otherwise. Then, there exists a vertex on the simple path $$$x\neq u,v$$$ which is the endpoint of exactly one edge on the path. Since the degree of all vertices must be even when considering symmetric difference of cycles, $$$x$$$ must be the endpoint of at least 1 other edge not on the path. But this can only occur if there exists another endpoint of one of the $$$C$$$ "special" edges in some other direction. In other words, rooting the tree at $$$x$$$, there exist at least 3 child subtrees with nodes in $$$S'$$$. This contradicts the earlier statement, and the result follows.
With this observation, we are able to consider the "virtual tree" of the original tree consisting only of vertices in $$$S'$$$: add an edge between two nodes $$$u$$$ and $$$v$$$ in the virtual tree if no other vertex in $$$S'$$$ is present on the simple path between $$$u$$$ and $$$v$$$ in the original tree. Now, we can compute the symmetric difference of cycles on this tree, reducing the time complexity of that part to $$$O(2^C\cdot C)$$$, from $$$O(2^C\cdot N)$$$.
Also, consider all edges on the "virtual tree" which represented more than one edge on the original tree. If this edge $$$(u,v)$$$ was included in the symmetric difference of cycles, and therefore removed from the original graph, there exists at least 1 intermediate vertex on that edge, which becomes disconnected from $$$u$$$ and $$$v$$$. Since this intermediate vertex is not in $$$S'$$$, by definition of virtual tree, no other edges connect this vertex to the rest of the graph. Therefore, the remaining graph becomes disconnected.
Therefore, if the virtual tree (with the addition of the unselected "special" edges) remains connected after removing some symmetric difference of cycles, then the original graph will also remain connected with that removal. We can compute the virtual tree in $$$O(N)$$$ using a DFS. This reduces the overall time complexity of the algorithm to $$$O(2^C\cdot C\cdot\alpha(C)+N)$$$.
With this optimisation, we can solve the problem for $$$N\le 10^6$$$, $$$C\le 20$$$ !
Sample code that implements this: https://codeforces.me/contest/2260/submission/398537962



