Блог пользователя M1v1savva

Автор M1v1savva, история, 4 года назад, По-английски

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?

  • Проголосовать: нравится
  • +12
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +45 Проголосовать: не нравится

You can use fft to calculate the number of paths of all lengths that go through the centroid.