Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

Gagandeep98's blog

By Gagandeep98, history, 4 weeks 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

»
4 weeks 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.

  • »
    »
    4 weeks 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.

  • »
    »
    4 weeks 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
»
4 weeks 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