Не гарантируется, что в запросах L < R.

Правильное решение:

ДП. f(vertex, cnt, closest) -- максимальное количество вершин, переходящих на новые сервисы в поддереве вершины vertex, если в её поддереве установлено cnt новых сервисов, а ближайший к vertex новый сервис расположен в closest. Важно, что closest не обязана находиться в поддереве vertex. Считаем, что в vertex расположен новый сервис, если closest = vertex. При подсчёте ДП для ребёнка u вершины vertex ближайшей вершиной к u с новым сервисом должна оказаться либо closest, либо любая вершина из поддерева u (но последнее возможно только в случае, если closest не находится в поддереве u). Сложность решения O(n³).

Accepted-решение:

Посчитаем cover(i, j) = 0/1 -- правда ли новый сервис, установленный в вершине i, "покроет" вершину j. Имеем n битовых масок длины n, из которых надо выбрать k так, чтобы в их объединении было как можно больше единичных битов. Выберем k случайных масок и 10000 раз попробуем сделать локальную оптимизацию: заменим случайную маску в множестве на случайную не из множества и посмотрим, улучшится ли ответ. Повторяем всю процедуру, пока не наступит TL.