Chandler-Bing's blog

By Chandler-Bing, history, 4 years ago, In English

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?

Full text and comments »

  • Vote: I like it
  • -28
  • Vote: I do not like it