#### 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

Auto comment: topic has been updated by EonHino (previous revision, new revision, compare).Using centroid decomposition we can find it in O(nlog^n) or at least O(nlog^2n).

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.

Can you explain more about it?

I have done a few problems with centroid decomposition but can't think of anything about this problem.

How can we use this technique to find the count of number of paths of length k in a tree for each k from 1 to n-1 at once?

That is this problem: https://judge.yosupo.jp/problem/frequency_table_of_tree_distance. Looks like you need to use FFT.

You don't need to do any decomposition. Root the tree arbitrarily, and for each vertex

uletS_{u}be the multiset of lengths of paths starting in the subtree ofuand ending inu. To compute it, initiallyS_{u}= {0} (the empty path), and then for each childvofuwe takelinS_{v}and addl+ 1 toS_{u}. If you merge small sets into larger sets this will run in time (you can resolve the + 1 by maintaining some additive constant for eachS_{u}).Then, to count the number of paths, notice that each path has some highest vertex it passes through, so in

uwe can compute all paths whose highest vertex isu. When we take a valuelinS_{v}we would like to find all paths coming from earlier subtrees ofuthat add up to a path of length at leastk. But this is just a range query (count all values in the multisetS_{u}that are at leastk- (l+ 1)). Note: doallrange queries forS_{v}before merging it intoS_{u}. So our set should support order statistics queries. You can use a treap or the GNU order statistics tree for this.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.

Do you have an implementation of this solution?