\begin{tutorial}{Горилла залезает на дерево}

\textbf{Решение 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)$.

\textbf{Решение 2}

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


\end{tutorial}
