Да, мы действительно написали n*log(n). И действительно TL. Видимо бага.
Если кто-то найдет её в алгоритме или пошлет мне хороший тест буду очень признателен.

// Генерил рандомные деревья (через снм), ежей, цепочки и т.п., на ноуте за 1.5 сек работает.

Условие:

В дерево T ответить на запросы radius[v, i] - количество вершин достижимых из v не более, чем за radius[v, i].
|T| <= 10⁵; |{radius[v, i]}| <= 3*10⁵

Решение:

1. У нас есть дерево =)
2. Дерево T можно поделить на две части L и R по вершине t, так что 1/3|T| <= |L|,|R| <= 2/3|T|
   см. далее подробнее
3. Для каждой вершины, для каждого запроса считаем ответ для L и R (рекурсивные запуски)
4. Для каждого расстояния d считаем
   lensL[d] = <количество вершин в L достижимых из t не более, чем за d шагов>
   lensR[d] = <количество вершин в R достижимых из t не более, чем за d шагов>
5. Для каждого запроса radius[v,i] к вершине v из L добавляем к ответу lensR[radius[v,i] - depth[v]]
   (это в точности количество вершин достижимых в правой половине из v, т.к. у нас L и R "соприкасаются" только в t)
   Для каждого запроса radius[v,i] к вершине v из R добавляем к ответу lensL[radius[v,i] - depth[v]]
6. Склеиваем деревья

Комментарии к пункту 2.
1) по ребру делить гораздо проще, но не для бинарного дерева это неверно =(
2) Что такое поделить по вершине - раздвоить ее, и некоторые ребра присоединить к одному образу, а некоторые - ко второму.
3) Как найти где делить:
   3.1 Ориентировать dfs-ом из 0.
   3.2 Им же подсчитать размеры поддеревьев, висящих на исходящих ребрах.
   3.3 двигаемся в ветку, размер которой >= 2/3|T| пока можем (дерево уже ориентировано, это O(|T|))
   3.4 утверждается, что теперь мы стоим в вершине, из которой все ребра выходят в ветки <= 2/3|T|
4) Как делить:
   4.1 подсчитать размеры поддеревьев, висящих на исходящих ребрах.
   4.2 наибольшую ветку из t пихаем в R
   4.3 пихаем в L все подветки из t, пока не наберем хотя бы 1/3|T|
   4.4 остальные ветки пихаем в R
5) Почему поделилось (доказательство)?
   5.0 1/3|T| <= |L|, |R| <=> |L|, |R| <= 2/3|T| <=> 1/3|T| <= |L| <= 2/3|T| <=> 1/3|T| <= |R| <= 2/3|T|
   5.1 x <= 2/3|T| (x - размер максимальной ветки из t). Так что, 4.3 нам всегда хватит веток для выполнения 1/3|T| <= |L|.
   5.2 допустим 1/3|T| <= x <= 2/3|T|. Тогда оставшиеся ветки в сумме не превосходят 2/3|T|, даже если все запихнуться в L, будет выполнено 1/3|T| <= R.
   5.3 если x <= 1/3|T|, то при добавлении в L очередной ветки |L| <= 2/3|T| (т.к. на предыдущем шаге |L| <= 1/3|T| и прибавили не более x). Значит 4.3 остановится при |L| <= 2/3|T|.

UPD: Замечания

Сережа (Burunduk1) предложил гораздо более простой способ разбиения по вершине:
1. Dfs ориентирует ребра и считает размеры поддеревьев.
2. Получая размер очередной подветки он прибавляет его к size[v], и, если оно превосходит 1/3|T|, то текущая вершина - это вершина, по которой необходимо разделить дерево, при чем подсчитанные ветки кладем в L, а не подсчитанные в R (ребро к предку тоже в R).

Почему это работает:
1. на каждом шаге размер всех учтенных подветок < 1/3|T| (база - это листья размера 1). Значит когда мы прибавляем к счетчику size[v] < 1/3|T| размер поддерева size[u] < 1/3|T|, результат будет не более 2/3|T|. Значит в вершине, в которой счетчик превзойдет 1/3|T| будет выполнено:
1/3|T| <= size[v] <= 2/3|T|, тогда построенные L, R тоже удовлетворяют этому соотношению.

Это один короткий dfs вместо двух длинных, особая бурундучья магия.