### EonHino's blog

By EonHino, history, 3 years ago,

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

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

• +10

 » 3 years ago, # |   0 Auto comment: topic has been updated by EonHino (previous revision, new revision, compare).
 » 3 years ago, # |   +8 Using centroid decomposition we can find it in O(nlog^n) or at least O(nlog^2n).
 » 3 years ago, # | ← Rev. 3 →   +10 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-TreeMaybe 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.
•  » » 3 years ago, # ^ |   0 Can you explain more about it?
•  » » 3 years ago, # ^ |   0 I have done a few problems with centroid decomposition but can't think of anything about this problem.
•  » » 5 weeks ago, # ^ |   +1 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?
•  » » » 5 weeks ago, # ^ |   +2 That is this problem: https://judge.yosupo.jp/problem/frequency_table_of_tree_distance. Looks like you need to use FFT.
 » 3 years ago, # | ← Rev. 4 →   +34 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.
•  » » 5 weeks ago, # ^ |   +3 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.
•  » » » 5 days ago, # ^ |   0 Do you have an implementation of this solution?