presumption's blog

Question about this Tree Problem
By presumption, history, 15 months ago, In English

Given a tree with $$$n$$$ vertices.
You are also given $$$q$$$ queries and each query is described by $$$2$$$ vertices of the tree.

You have to count the number of times each vertex was visited after processing all the queries.
Processing a query means you travel form one vertex in that query to other vertex and you visit all the vertices including the starting vertex, ending vertex, and all the other vertices in the path once.

My Questions about the Problem:

  • Is it possible to solve the above problem if $$$1 ≤ n ≤ 10^5$$$ and $$$1 ≤ q ≤ 10^5$$$?
  • What are the steps or algorithm for solving this problem?
  • Is their any data structure or algorithm which can be used if after some queries we are asked how many time a particular vertex has been visited?
  • Vote: I like it
  • +1
  • Vote: I do not like it

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by presumption (previous revision, new revision, compare).

→ Reply
»
15 months ago, # |
← Rev. 3   Vote: I like it +15 Vote: I do not like it

first into the cases of $$$\text{LCA}(u,v)\in[u,v]$$$ and $$$\text{LCA}(u,v)\notin[u,v]$$$. For the former, it is just a vertical chain plus $$$1$$$, and for the latter, it is two chains plus $$$1$$$.

Consider a diff on the tree, then for each chain $$$(u,v)$$$ the operation of adding one is transformed into diff[u]++ diff[father[v]]--.

And querying the value of a point becomes querying the sum of all values in the subtree. By tiling the tree as an array with dfn, the subtree numbers of each node must be consecutive, so we can use segment tree to maintain this answer.

An additional example to facilitate understanding.

garph

This is the case of 8~11, where the difference array changes to

diff[6]++
diff[11]++
diff[father[4]]-=2

Then if I want to ask for a value of 5, the corresponding diff array is diff[7~11]

→ Reply
  • »
    »
    15 months ago, # ^ |
    ← Rev. 3   Vote: I like it +6 Vote: I do not like it

    Do we need to use Heavy Light Decomposition for this problem? I am not getting the part where we need to handle the subtrees. As ther the query won't always be consecutive right as Depth First Numbering will enter some subtree first then another one? Thanks for the approach.

    → Reply
    • »
      »
      »
      15 months ago, # ^ |
        Vote: I like it +7 Vote: I do not like it

      Heavy Light Decomposition is absolutely adequate. But since we have a simpler way to do it, there is no need to use this.

      You may think that the chain dfn is discontinuous, but in my method there is no operation on the chain, but the summation of the entire subtree (because the difference is performed). You can easily prove subtree dfn is continuous by considering a Cartesian tree-like structure.

      → Reply
»
15 months ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

This problem can be solved in O(nlogn) order using LCA(binary lifting) and difference array technique on tree. No need of heavy light Decomposition

→ Reply