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



