Union and Intersection of Tree and Path Neighborhoods

2026-01-10enucai1 min read (212 words)

#oi #algorithm #paper

This article is the author’s National Training Team paper.

Abstract#

This paper introduces the theory of tree neighborhoods, methods for finding the union and intersection of tree neighborhoods, and the theory and algorithms for the intersection of path neighborhoods on trees. Furthermore, it presents several applications of these methods to related problems.

Introduction#

Tree-structured problems are crucial subjects of study in algorithmic competitions, among which tree neighborhood problems are highly common.

Starting from the concept of neighborhoods on trees, one can naturally draw an analogy to circular domains in planar geometry. Research reveals that when performing operations such as union and intersection, tree neighborhoods exhibit structural properties and aesthetic symmetry similar to those of planar circles. When further generalized to path neighborhoods on trees, these elegant structural properties are still preserved to a certain extent.

This paper will focus on the union and intersection operations of tree neighborhoods, as well as the intersection operations of path neighborhoods on trees. It will also provide simple analyses and discussions of the relevant properties in conjunction with specific problems.