Centroid decomposition problem

Revision en1, by M1v1savva, 2020-11-23 09:06:36

The problem is the following:

Given a tree on $$$n$$$ vertices. For each $$$d = 1, 2, ..., n - 1$$$ find the number of paths of length $$$d$$$.

$$$n$$$ <= 50000, 5 seconds, 256 mb

I know how to solve similar problem with fixed $$$d$$$ using CD but have no clue how to solve this version. Could someone help?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English M1v1savva 2020-11-23 09:06:36 326 Initial revision (published)