Задача 1
Дано корневое дерево и число $$$k$$$. Для каждой вершины $$$u$$$ найти кол-во вершин в поддереве вершины $$$u$$$ отдаленных от $$$u$$$ на расстояние не более $$$k$$$ рёбер.
Задача 2
Дано дерево и число $$$k$$$. Для каждой вершины $$$u$$$ найти кол-во вершин во всем дереве отдаленных от $$$u$$$ на расстояние не более $$$k$$$ рёбер. (источник) (похожая задача)
В этом блоге рассмотрим решение Задачи 1 за $$$O(N)$$$. При этом используется забавная структура — RQ на stack-е с запросами $$$O(1)$$$ (по сути это будет префикс-сумма).
Вообще Задача 1 возникла при попытке (видимо не удачной) решить Задачу 2, для которой есть решения за $$$O(N \ln N)$$$, но я пока не знаком с этими темами и не хочу напутать:
через Centroid Decomposition
для похожей задачи через SplayTree и прочее (см. комментарии про задачу D)
