Дано дерево на n
вершинах (связный неориентированный ациклический граф c n−1
рёбрами), где у каждого ребра есть вес w
. Назовём простой путь длины k
возрастающим , если существует такое целое x>=
2, что вес первого ребра пути делится на x
, второго ребра — делится на x2
, ……, вес k
-го ребра делится на xk
.
Требуется найти максимальную длину k
возрастающего пути, где k
— количество рёбер в нём.
Входные данные
В первой строке вводится единственное целое число n
(1 <= n
<= 100000) - число вершин в дереве.
В следующих n−1
строках вводятся по три целых числа u
, v
, w
( 1<= v
<= n, 1<= w
<= n, u ≠ v, 1 <= w
<= 107) - номера вершин, которые соединяет очередное ребро, и его вес.
Выходные данные
Выведите одно целое число k -
максимальную длину возрастающего пути.
Примечание
Простым путем называется такой путь, что все вершины в нем различны.
В 1-м примере есть путь длины 2: 3 — 1 — 2. Тогда для него подходящий x = 2
. Можно показать, что возрастающего пути большей длины не существует.
Во 2-м примере есть путь длины 3: 3 — 4 — 5 — 6. Тогда для него подходящий x = 2
. Можно показать, что возрастающего пути большей длины не существует.
Примеры
№ |
Входные данные |
Выходные данные |
1 |
4
1 2 8
1 3 6
1 4 3
|
2
|
2 |
6
1 2 2
2 3 4
3 4 2
4 5 4
5 6 8
|
3
|