querying if ancestor of a vertex appears in a subarray

Правка en1, от whatthemomooofun1729, 2023-09-10 10:26:27

I have been thinking about the following problem lately: we are given a tree (rooted at vertex 1) and an array. We want to answer some queries. In each query, we are given a vertex v and two indices L and R, and we want to output the "YES" or "NO". The answer is "YES" if on the subarray from L to R, there exists a vertex u such that v belongs to the subtree of u.

I could think of a solution with quadratic time complexity (loop from L to R and check if u exists), which is not efficient.

Another thought I had was to maintain two arrays tin and tout, which store the time when we process the vertex and when we finish processing the vertex. Then, we just need to check if there exists u on the subsegment such that tin[u] <= tin[v] and tout[u] >= tout[v], but I haven't thought of how to get solution from this.

Do you have idea how to solve this? Thanks!

Теги range query, tree

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский whatthemomooofun1729 2023-09-10 10:26:27 922 Initial revision (published)