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?

The problem is the following:

We have array $$$a$$$ of $$$n$$$ integers and for each integer $$$k$$$ from $$$1$$$ to $$$n$$$ we want to calculate the number of pairs $$$(i, j)$$$ such that $$$a_i + a_j = k$$$.

I wonder if it can be solved in less than $$$\mathcal{O}(n^2)$$$

UPD: turns out it is a classical FFT problem