Задача №114577. Возрастающие пути
Дано дерево на \(n\) вершинах (связный неориентированный ациклический граф c \(n-1\) рёбрами), где у каждого ребра есть вес \(w\).
Назовём простой путь длины \(k\) возрастающим , если существует такое целое \(x \geq 2\), что вес первого ребра пути делится на \(x\), второго ребра — делится на \(x^2\), \(\ldots\), вес \(k\)-го ребра делится на \(x^k\).
Требуется найти максимальную длину \(k\) возрастающего пути, где \(k\) — количество рёбер в нём.
В первой строке вводится единственное целое число \(n\) (\(1 \leq n \leq 100\,000\)) — число вершин в дереве.
В следующих \(n - 1\) строках вводятся по три целых числа \(u\), \(v\), \(w\) (\(1 \leq u \leq n\), \(1 \leq v \leq n\), \(u \ne v\), \(1 \leq w \leq 10^7\)) — номера вершин, которые соединяет очередное ребро, и его вес.
Выведите одно целое число \(k\) — максимальную длину возрастающего пути.
Простым путем называется такой путь, что все вершины в нем различны.
В \(1\)-м примере есть путь длины \(2\): \(3\) — \(1\) — \(2\). Тогда для него подходящий \(x = 2\). Можно показать, что возрастающего пути большей длины не существует.
Во \(2\)-м примере есть путь длины \(3\): \(3\) — \(4\) — \(5\) — \(6\). Тогда для него подходящий \(x = 2\). Можно показать, что возрастающего пути большей длины не существует.
Тесты к этой задаче состоят из пяти групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов некоторых из предыдущих групп. Обратите внимание, прохождение тестов из условия не требуется для некоторых групп. Offline-проверка означает, что результаты тестирования вашего решения на данной группе станут доступны только после окончания соревнования.
| Группа | Балл | n | Дополнительно | Зависимости |
| 0 | 0 | Тесты из условия | ||
| 1 | 28 | \(n \le 1000\) | 0 | |
| 2 | 12 | \(n \le 100\,000\) | Степени вершин не больше двух | |
| 3 | 20 | \(n \le 100\,000\) | Веса рёбер — степени двойки | |
| 4 | 11 | \(n \le 100\,000\) | Вес каждого ребра не больше \(10000\) | 0 |
| 5 | 29 | \(n \le 100\,000\) | Offline-проверка | 0–4 |
4 1 2 8 1 3 6 1 4 3
2
6 1 2 2 2 3 4 3 4 2 4 5 4 5 6 8
3