Interesting property of trees

Revision en3, by gelastropod, 2026-11-15 08:54:48

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

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)