Gagandeep98's blog

Stuck On CSES Problem Counting Paths: Please Provide Any Hint
By Gagandeep98, history, 5 years ago, In English

I am stuck on Counting Path 1136 problem, and unable to think how to write an approach optimal to given constraints. Any hint or help is highly appreciated.

I cannot find any place where there is any hint for CSES problems(Except DP and Range Queries), hence thought this as the only possible option.

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

Comments Comments (19)
| Write comment?
»
5 years ago, # |
← Rev. 4   Vote: I like it +13 Vote: I do not like it

Seems like a classic LCA + Segment tree problem.

Flatten the tree using dfs and update on the range by 1 from index of a to index of b for every path. (Update the subtree of LCA(a,b) by 1 and the subtrees of node a and node b by -1 (dont forget to update extra 1 for node a and node b specifically)).

There are edge cases, make sure you handle them.

Print all the segment tree values for all nodes in the end.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Thank you! But why is segment tree needed? I think LCA + array for range is sufficient.

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

    Can you please clarify one thing? Suppose I had a tree as shown below :

    EXAMPLE TREE

    Now let us assume that for the current path a=7 and b =5. So according to your algorithm, we will first find the of lca of a and b so here lca(a,b)=1 and then we'll add 1 to the subtree of node 1 and then add -1 to subtree of node 5 and node 7 (in this way we took care of nodes 10,11,12 and 9 that no update is made on them) but what about nodes 4,8 and 6 shouldn't we subtract 1 from them too? Sorry if I asked something very obvious or interpreted your algorithm incorrectly.
    EDIT: Got an AC by using (kind of)prefix sum approach using lca on the tree

    CODE FOR REFERENCE
    → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    ViciousCoder can you please clear a bit more..

    i was thinking of doing +1 on a range of tin[lca] to tout[lca] and -1 on tin[a] to tout[a] and tin[b] to tout[b]

    but clearly this is not covering all cases..

    can you please specify the segments you would carry out the operation on?

    (i understood what needs to be done without seg trees but i am looking for a soln with seg tree)

    mycode without seg tree: https://ideone.com/1NJn9n

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

    using LCA is enough to solve problem. I can suggest 3 tags for the problem, LCA, Math, Scanline.

    → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +2 Vote: I do not like it

There are complicated data structure solutions to this problem. But this one can actually be solved by doing prefix sums on difference array on tree.

Break down each path into two vertical paths. Now, for each vertical path, in some vertex indexed array, do +1 for deeper point of vertical path and -1 for higher point.

After this, just do subteee sum of values in the vertex indexed array. It will represent paths going out of a vertex, which is what you wanted.

78837236 Accepted solution for an almost same problem on Codeforces

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

    Thanks a ton, it really helped a lot !!

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

ViciousCoder can you please share your solution using segment trees?

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

simple dfs + LCA is enough for this problem. dont need any DS.
code

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

One sol is the following:
maintain a counter on each node.
If a path is given as (a , b), modify the counters as
counter[a]++ , counter[b]++ , counter[lca(a , b)]-- , counter[parent(lca(a , b))]--.
The answer is the sum of counters of a subtree.

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

    can you please tell me why it works? if there are any prerequisites please tell me

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

      Split a path (a , b) into 2 parts: a -> lca(a , b) and lca(a , b) -> b.
      You want to increment all nodes in these paths or at least simulate such a thing. Since directly incrementing each node is too slow, lets denote the answer for each node as the sum of its subtree.


      Now, if we want to include the path a -> lca(a , b), we just increment the node a. But now, any ancestor of lca(a , b) also has a in its subtree but SHOULDNT be included in the path. Hence, we decrement parent(lca(a , b)) by one, so that node and all its ancestors dont include a. This idea is analogous to prefix sums.

      Now lets do path b -> lca(a , b). If we increment b, all nodes above it will also be incremented. However, notice that we have already incremented lca(a , b) in the previous path, so we are over counting that. Hence we decrement lca(a , b) by one.

      In total, the operation boils down to incrementing a and b by one. Now every node in the path a -> b has been increased by 1 except the lca ( which has been increased by 2 ). Furthermore, every ancestor of the lca has also been increased by 2. To counter this, we subtract one from the lca ( to make it 1 and all nodes above it 1 ), and one from the parent of the lca (to make it 0 and all nodes above it 0).


      Not sure if that made any sense, but hope that helps :)

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

        Thank you, i really understood it now!!!

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

    Hi there,i tried same approach but getting some problems, can you share your implementation

    → Reply