Горилла залезает на дерево

Решение 1

Давайте зафиксируем вершину $$$v$$$ и решим задачу для неё.

Оценим количество рёбер, по которым горилла успеет подняться до того как устанет или доберётся до корня. К сожалению, таких рёбер может быть много. Покрасим рёбра веса $$$1$$$ в красных цвет. Пусть не покрашенных рёбер $$$p$$$, тогда произведение весов на них хотя бы $$$2^p$$$. Значит $$$p \le \log_2 k \le 30$$$.

То есть путь от вершины $$$v$$$ до искомой будет состоять из путей, все рёбра которых имеют вес один, соединённых не более $$$30$$$ рёбрами веса больше $$$1$$$. То есть надо научиться подниматься из вершины в ближайшую вершину, на пути до которой встречается ребро веса хотя бы $$$2$$$.

Несложно насчитать динамику, которая будет хранить ближайшего предка, на пути до которого встречается ребро веса хотя бы $$$2$$$. Либо этот предок является нашим родителем (если вес ребра в него хотя бы $$$2$$$), либо мы должны взять значение динамики от нашего родителя (если вес ребра в него $$$1$$$).

Таким образом, выполнив предпосчёт за $$$O(n)$$$, можно независимо решить задачу для всех вершин за $$$O(n \log k)$$$.

Решение 2

Построим двоичные подъёмы за $$$O(n \log n)$$$. Будем решать задачу для фиксированной вершины прыжками по бинподъёмам. То есть будем искать момент, в который произведение на пути длины степень двойки станет больше $$$k$$$. Проверка на отсутствие переполнения при прыжке по бинподъёмам остаётся в качестве упражнения читателю.