Задача №114702. Доставка посылок
В городе Nске есть \(n\) домов, которые соединены \(n - 1\) двусторонней дорогой так, что от любого дома можно доехать до любого другого, передвигаясь по дорогам. В каждом доме проживает ровно один человек.
В один праздничный день в качестве подарка каждый житель города решил отправить каждому посылку. Посылки в Nске доставляет специальная бесконтактная почта. Чтобы доставить жителю дома \(u\) посылку от жителя дома \(v\), почтовый курьер забирает посылку около дома \(v\), затем едет по кратчайшему пути до дома \(u\) и оставляет посылку около него.
К сожалению, в Nске действуют строгие правила отправки посылок. Вес каждой посылки должен быть целочисленным, а также для каждой дороги установлено целое число \(w_i\) — ограничение на провоз посылок, означающее, что по этой дороге можно провозить только посылки, вес которых делит \(w_i\). Иными словами, посылка веса \(x\) может быть провезена по дороге с ограничением \(w_i\) только если \(w_i\) делится нацело на \(x\).
Жители города очень любят праздники, поэтому каждый житель решил отправить каждому посылку наибольшего возможного веса.
Чтобы обеспечить наилучшую работу бесконтактной почты, необходимо посчитать суммарный вес всех отправленных посылок. Помогите решить эту важную задачу!
Первая строка содержит целое число \(n\) (\(2 \leq n \leq 100\,000\)) — количество домов в городе.
Каждая из следующих \(n - 1\) строк содержит описание дороги: три целых числа \(u_i\), \(v_i\) и \(w_i\) (\(1 \leq u_i, v_i \leq n\), \(u_i \neq v_i\), \(1 \leq w_i \leq 10 ^ 6\)) — номера домов, между которыми проложена \(i\)-я дорога, и ограничение на провоз посылок в \(i\)-й дороге. Дома в городе нумеруются, начиная с единицы.
Гарантируется, что между каждой парой домов существует путь по дорогам.
Выведите единственное число — сумму весов всех отправленных жителями посылок.
В первом примере из условия житель 1 мог отправить жителю 2 посылку веса не более 6, аналогично житель 2 мог отправить жителю 1 посылку веса не более 6. Житель 1 мог отправить жителю 3 посылку веса не более 4, аналогично житель 3 мог отправить жителю 1 посылку веса не более 4. Житель 2 мог отправить жителю 3 посылку веса не более 2, так как число 6 должно делиться на вес посылки, и число 4 должно делиться на вес посылки. Аналогично житель 3 мог отправить жителю 2 посылку веса не более 2.
В таблице ниже отмечены максимальные веса, которые могут отправить друг другу жители во втором примере из условия.
| Житель | 1 | 2 | 3 | 4 | 5 | 6 |
| 1 | – | 4 | 1 | 10 | 2 | 5 |
| 2 | 4 | – | 1 | 2 | 2 | 1 |
| 3 | 1 | 1 | – | 3 | 1 | 1 |
| 4 | 10 | 2 | 3 | – | 2 | 5 |
| 5 | 2 | 2 | 1 | 2 | – | 1 |
| 6 | 5 | 1 | 1 | 5 | 1 | – |
Тесты к этой задаче состоят из восьми групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов необходимых групп. Offline-проверка означает, что результаты тестирования вашего решения на данной группе станут доступны только после окончания соревнования.
| Доп. ограничения | |||||
| Группа | Баллы | \(n\) | \(w_i\) | Необх. группы | Комментарий |
| 0 | 0 | – | – | – | Тесты из условия. |
| 1 | 14 | \(n \le 500\) | \(w_i \leq 100\,000\) | 0 | |
| 2 | 11 | \(n \le 3000\) | – | 0, 1 | |
| 3 | 12 | – | – | – | Все \(w_i\) простые числа.* |
| 4 | 15 | – | – | – | \(u_i = 1, v_i = i + 1\) |
| 5 | 16 | – | – | – | \(u_i = i, v_i = i + 1\) |
| 6 | 10 | – | \(w_i \leq 500\) | 0 | |
| 7 | 8 | – | \(w_i \leq 10\,000\) | 0, 6 | Offline-проверка. |
| 8 | 14 | – | – | 0–7 | Offline-проверка. |
*Простым числом называется число, имеющее ровно два различных натуральных делителя — единицу и самого себя.
3 1 2 6 1 3 4
24
6 1 2 4 3 4 3 1 4 10 5 1 2 4 6 5
82