EonHino's blog

The number of path in tree that have at least length k.
By EonHino, history, 5 years ago, In English

Statement

Given an undirected tree, count how many paths that have at least length of k.

Input

The first line is n (n <= 10 ^ 5) and k (k <= n) — the number of vertices and k as mentioned above.

Next n — 1 line represents an edge.

5 2

1 2

2 3

2 4

4 5

Output

6

Explain

All paths that have at least length of k:

(1,3): 1-2-3

(1,4): 1-2-4

(1,5): 1-2-4-5

(2,5): 2-4-5

(3,4): 3-2-4

(3,5): 3-2-4-5

  • Vote: I like it
  • +10
  • Vote: I do not like it

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

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

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

Using centroid decomposition we can find it in O(nlog^n) or at least O(nlog^2n).

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

It can be solved with centroid decomposition + Fenwick tree or seg tree in O(N*log^2(N))

If you are not familiar with centroid decomposition this might help : https://threads-iiith.quora.com/Centroid-Decomposition-of-a-Tree

Maybe there is a faster or better solution, but I think this idea is enough to solve it if the time constrains are not too tight.

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

You don't need to do any decomposition. Root the tree arbitrarily, and for each vertex u let Su be the multiset of lengths of paths starting in the subtree of u and ending in u. To compute it, initially Su = {0} (the empty path), and then for each child v of u we take l in Sv and add l + 1 to Su. If you merge small sets into larger sets this will run in time (you can resolve the  + 1 by maintaining some additive constant for each Su).

Then, to count the number of paths, notice that each path has some highest vertex it passes through, so in u we can compute all paths whose highest vertex is u. When we take a value l in Sv we would like to find all paths coming from earlier subtrees of u that add up to a path of length at least k. But this is just a range query (count all values in the multiset Su that are at least k - (l + 1)). Note: do all range queries for Sv before merging it into Su. So our set should support order statistics queries. You can use a treap or the GNU order statistics tree for this.

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

    Actually you can do it in $$$\mathcal{O}(n)$$$: you don't need sets, you can just return a vector (have depth $$$0$$$ in the last element, so you can increase depth by pushing an element to the back). When we merge a smaller set to a larger set, the size of the larger set doesn't increase. Thus, every vertex contributes to only one merge. We can maintain prefix sums on counts at depths while merging.

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

      Do you have an implementation of this solution?

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

      Here is my implementation using mango_lassi's idea.

      mango_lassi Can you take a look and suggest any optimization / better implementation?

      C++ code

      EonHino Is there anywhere I can submit this solution?

      → Reply