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?
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 of this property
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$$$.
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. Now, take an arbitrary spanning tree of the graph. Each of the $$$C = M - (N - 1)$$$ edges 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$$$ combinations of cycles in the basis. Now, for each edge in the tree, if it is used in an odd number of cycles, we label it with $$$1$$$, and $$$0$$$ otherwise. A cycle is valid if: a) the $$$1$$$-edges create a simple cycle as a subcycle, and b) the $$$0$$$-edges suffice to connect all nodes in the graph.
The final complexity of the solution is $$$O(2^C \cdot (N + M))$$$.



