Pawan_Lahoti's blog

(Doubt)Cses Fixed-Length Paths I
By Pawan_Lahoti, history, 17 months ago, In English

I know about centroid decomposition but I cannot understand the solution given on USACO guide...Can someone please give a simple explanation to this problem https://cses.fi/problemset/task/2080

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

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

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

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

We are exploiting the fact that for any two nodes (u,v), the lca in their centroid tree divides it into two disjoint paths.

Thus when we find a centroid, we effectively want to calculate the summation of cnt_i[x] * cnt_j[y] where cnt_i denotes the cnt of depth = x in child i of centroid and x + y == k. Because of the above mentioned fact, we won't get any repetition.

Time complexity: for each layer of centroids , we will do O(N) operations and because the height of centroid tree is limited to log(N), Time Complexity will be O(Nlog(N)).

→ Reply