pratheekrai2002's blog

Need help in a question
By pratheekrai2002, history, 16 months ago, In English

Sorry if the question had been asked before, but I needed help in the following problem, any hints or topics from which it is based on would be helpful : given a tree with n nodes with each node containing a value a[i] associated with node i, also you have q queires containing of 2 nodes u and v, and a value t, you need to find the no of nodes in the simple path between u and v that have a value of atmost t? n<=1e5 q<=1e5 1<=u,v<=n t<=1e9

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
16 months ago, # |
  Vote: I like it -6 Vote: I do not like it

hld

→ Reply
  • »
    »
    16 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    could you please elaborate on how heavy light decomposition could be used to solve the problem?

    → Reply
    • »
      »
      »
      16 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      you can use hld to transform any problem "count X in the simple path" to "count X in segment of array".

      After the transformation you will get the classic problem.

      how to solve on the segment
      → Reply
»
16 months ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

Since you don't need updates, you can use Euler Tour to get the sum in the path between nodes. You take note the instant you enter and leave a node in DFS, then you sort the queries by $$$t$$$ and the nodes by $$$a[i]$$$, you insert in (segment tree/Fenwick tree) a $$$+1$$$ in when you enter the node and a $$$-1$$$ when you leave it, do this for all nodes with $$$a[i]$$$ less than or equal to your current $$$t[j]$$$, then you can get the answer with prefix sums: $$$queryfenwick(enter[u]) + queryfenwick(enter[v]) - 2 * queryfenwick(enter[lca(u, v)]) + val[lca(u,v)]$$$

→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you for your inputs sir, I was thinking of something similar but wasn't getting the jist of it. I had a small doubt tho, what does queryfenrick[enteru] represent? Say for example I had the following tree of 4 nodes: 1-2 , 1-3 , 3 -4, assume for simplicity the values are (1, 2 ,3 4 ) that is a(i)=i, now the Euler path considering 1 as root will be (1 2 2 3 4 4 3 1) right? So we have in(1) = 1 , out(1) = 8, in(2) = 2, out(2) =3, in(3) = 4, out (3) = 7, in (4) = 5 and out(4) =6. Now suppose our first query in sorted order is u = 2 , v = 3 and t = 2, so initially the value array based on Euler's tour is 0 0 0 0 0 0 0 0, then you are saying to update the Val array using segment tree and add a +1 and -1 for the nodes 1 and 2, as it's a(i)<=2, so the new value array is 1 1 -1 0 0 0 0 -1, right? Now could you please elaborate how to find the values in the path from 2 to 3, in this array using segment tree?

    → Reply
    • »
      »
      »
      16 months ago, # ^ |
      ← Rev. 2   Vote: I like it +1 Vote: I do not like it

      You are right, the prefix sum of the array in position $$$in[u]$$$ is equal to sum of the nodes from the $$$root$$$ to $$$u$$$, you can interpret this as the instant you are visiting that node in DFS you will ignore the values of all the nodes that are not in the path from the $$$root$$$ to $$$u$$$. You need to calculate the LCA(Lowest Common Ancestor) of u and v (this can be done also with Euler Tour), then the answer is equal to the sum of the prefix of $$$in[u]$$$ and $$$in[v]$$$ minus the value of two times the prefix sum of $$$in[LCA(u, v)]$$$, because you are summing this part two times, then you add the single value of $$$in[LCA(u, v)]$$$ since you removed it.

      → Reply