Interesting property of trees

Revision en4, by gohchingjayk, 2026-11-15 09:22:22

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))$$$.

Tags trees

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en10 English gelastropod 2026-11-15 10:35:59 0 (published)
en9 English gohchingjayk 2026-11-15 10:26:18 22 Tiny change: 'nclusive).\n\nNow, c' -> 'nclusive). </p>\n\nNow, c'
en8 English gohchingjayk 2026-11-15 10:19:20 40 Use codeforces link instead of hyperlink
en7 English gelastropod 2026-11-15 10:15:13 94
en6 English gelastropod 2026-11-15 10:13:07 7 minor edits
en5 English gelastropod 2026-11-15 10:09:02 2942 Describe optimisation to solution
en4 English gohchingjayk 2026-11-15 09:22:22 1446 Describe solution to original problem
en3 English gelastropod 2026-11-15 08:54:48 12 Tiny change: 'nd $pre_v$.\n\nNow, ' -> 'nd $pre_v$ (inclusive).\n\nNow, '
en2 English gohchingjayk 2026-11-15 08:48:44 1091 Wrote down and proved the property
en1 English gelastropod 2026-11-15 07:28:24 23 Initial revision (saved to drafts)