RMQ on tree within a fixed distance

Revision en1, by Chandler-Bing, 2020-07-27 15:27:12

You are given a rooted tree with $$$N \leq 10^{5}$$$ nodes where node $$$1$$$ is the root. Each node $$$i$$$ has an integer value $$$C_{i}$$$. You are also given $$$Q \leq 10^{5}$$$ queries. In each query, you are given a node $$$V > 1$$$ and an integer $$$D$$$. Let $$$S$$$ be the set of nodes such that each element $$$U$$$ of $$$S$$$ satisfies following two conditions:

  • The distance between node $$$1$$$ and node $$$U$$$ is less than the distance between node $$$1$$$ and node $$$D$$$.
  • The distance between node $$$U$$$ and node $$$V$$$ is at most $$$D$$$.

For each query, you have to find the minimum $$$C_{i}$$$ for each element $$$i$$$ of $$$S$$$.

I know path queries in a tree can be performed using Heavy Light Decomposition and subtree queries can be performed using Euler Tour. But I don't know how to handle this kind of queries. How to solve this?

Tags #rmq, #tree

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Chandler-Bing 2020-07-27 15:27:12 830 Initial revision (published)