It is not uncommon to have interactive tree problems where you are allowed to query some connected component of the tree and use the return value to determine whether the answer is in the connected component or outside the connected component (Link to example problem). The general approach for these kinds of problems is to always choose a connected component of size $$$\frac{N}{2}$$$. However, there are also problems where the allowed queries are more restricted, preventing $$$\frac{N}{2}$$$ halving from being possible. This blog covers one of those types of problems.
Definitions
- Subtree: $$$S(r, u)$$$ contains the set of vertices in the subtree of vertex $$$u$$$ if the tree was rooted at vertex $$$r$$$.
- Neighbour: $$$N(u)$$$ contains the set of vertices that are directly adjacent to vertex $$$u$$$.
- Enhanced subtree: $$$ES(r, V) = \bigcup_{v\in V} S(r, v)\text{ if } v\in N(r)$$$. In other words, an enhanced subtree is a combination of the subtrees of a chosen set of vertices that are directly adjacent to the root.
Problem Structure
There is a hidden special vertex in a tree with $$$n$$$ vertices. Find the special vertex using at most $$$\left\lceil\log_{1.5}n\right\rceil$$$ of the following query:
- Choose an enhanced subtree of the tree. The grader will return whether the special vertex is in the chosen enhanced subtree. More formally, choose any vertex $$$r$$$ and a subset of neighbours $$$V \subseteq N(r)$$$, then the grader will return whether the special vertex $$$x \in ES(r, V)$$$.
