carnage17's blog

By carnage17, history, 5 years ago, In English

Here is the problem link and problem statement is pretty short you can have a go at it.
I was able to get 30 points on this question and then I thought if there is a way to order the queries to reduce time complexity but wasn't able to come up with anything.

Even though the editorial is pretty clear I am not able to understand it, Can someone share their approach on how to solve this problem.

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

| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I solved that problem with LCA

»
5 years ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

The idea is to have the information stored for all the nodes up to a parent that is at a distance of 2 ^ k. Now the problem is the following:

1 — First of all, to have the information stored, you need a precalculation and you have to know for each node the number of paths in the sub-tree of the parent node of u that pass only for the parent u and not for u. Now with that information we can have saved the solution for each node by uploading to a parent at a distance of 2 ^ k.

2 — After uploading each node to the LCA (u, v) you have to take into account other paths that were left uncounted, for example we do not count the number of roads that pass only by u and only by v from their respective sub-trees unless that one of the two is the LCA(u, v) and the amount is equal to: The number of paths that start from the sub tree of v and pass through v and not by any of their parents is equal to: Let's say that for son u of v has sub[i] nodes in his subtree then that amount of paths can be found in the following way ans = sub[v] + (sub[i1] * sub[i2]) + (su [i1] * sub[i3]) + ... (sub[i1] * sub[in]) + (sub[i2] * sub [i3]) + .... sub [in-1] * sub [in]

and also missing the paths that come from above the LCA(u, v) rooting the tree from any node by default but it is very easy to calculate.

And in the end you have the preprocessing in O (n log n) and the queries in O (log n).

For more clarity see my code.

my solution

Excuse me for my English grief.