algorithmtreetime-complexitydepth-first-searchlowest-common-ancestor

Queries on Tree Path with Modifications

Question:

You are given a Tree with n Nodes(can be upto 10^5) and n-1 bidirectional edges. And lets say each node contains two values:

  1. It's index(Just a unique number for node), lets say it will be from 1 to n.
  2. And It's value Vi, which can vary from 1 to 10^8

Now there will be multiple same type of queries(number of queries can be upto 10^5) on this same tree, as follows:

  1. You are given node1, node2 and a value P(can vary from 1 to 10^8).

And for every this type of query, you just have to find number of nodes in path from node1 to node2 whose value is less than P.

NOTE: There will be unique path between all the nodes and no two edges belong to same pair of nodes.

Required Time Complexity O(nLog(n)) or can be in other terms but should be solvable in 1 Sec with given constraints.

What I have Tried:

(A). I could solve it easily if value of P would be fixed, using LCA approach in O(nLog(n)) by storing following info at each node:

  1. Number of nodes whose value is less than P, from root to given node.

But here P is varying way too much so this will not help.

(B). Other approach I was thinking is, using simple DFS. But that will also take O(nq), where q is number of queries. Again as n and q both are varying between 1 to 10^5 so this will not help too in given time constraint.

I could not think anything else. Any help would be appreciated. :)

Source:

I read this problem somewhere on SPOJ I guess. But cannot find it now. Tried searching it on Web but could not find solution for it anywhere (Codeforces, CodeChef, SPOJ, StackOverflow).

Solution

    1. Let ans(v, P) be the answer on a vertical path from the root to v and the given value of P.

    2. How can we compute it? There's a simple offline solution: we can store all queries for the given node in a vector associated with it, run the depth-first search keep all values on the current path from the path in data structure that can do the following:

      • add a value
      • delete a value
      • count the number elements smaller than X

      Any balanced binary-search tree would do. You can make it even simpler: if you know all the queries beforehand, you can compress the numbers so that they're in the [0..n - 1] range and use a binary index tree.

    3. Back to the original problem: the answer to a (u, v, P) query is clearly ans(v, P) + ans(u, P) - 2 * ans(LCA(u, v), P).

    That's it. The time complexity is O((N + Q) log N).