So the question is, for each node $$$v$$$ in the tree you have to root the tree at $$$v$$$ then calculate the subtree sizes $$$s_u$$$ of all such $$$u$$$ where $$$u$$$ is a child of v and calculate $$$ \sum_{0 <= x_u <= k/2, \sum_{u}^{} x_u = k}^{} \prod_{u}^{} \binom{s_u}{x_u} \ $$$. I tried this using fft, for each of its child I can create a polynomial of size k and multiply them using DnC. However, this is too slow for $$$n, k <= 1e5$$$. I was looking at this editorial of finding no of pairs of nodes with prime distance but was unable to figure out what is "split of nodes" and why binarizing decreased the overall time complexity. (I am aware centroid decomposition and small to large solutions exist for the related problem but as mentioned in a comment for a dense series they won't work, anyways, point is that I want to apply fft on trees fast). Can somebody familiar with this idea please explain ?