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 ?

Link. This problem appeared in ICPC Amritapuri 2022 Qualifier Round and here with lower constraints. Please help.

You are given n points in the x-y plane and a rectangle of given height and width whose sides are aligned with the coordinate axes. You need to tell if you are allowed to translate the rectangle parallel to the axes what is the maximum no of points that can lie inside the rectangle at any point in time.

Yesterday, I quickly realized that the ABC's problem F was essentially this but could not find an optimal solution.