n вышек связи пронумерована от 0 до n − 1 и соединена кабелями в дерево: cables[i] = [a, b, w] — кабель длины w между вышками a и b. Количество вышек равно len(cables) + 1.
Сигнал восстанавливается каждые step единиц длины, поэтому вышка c может работать ретранслятором для пары вышек a < b, если:
- a ≠ c и b ≠ c;
- длина пути от c до a и длина пути от c до b делятся на step;
- пути от c до a и от c до b не имеют общих кабелей, то есть уходят из c в разные стороны.
Верните массив длины n, где i-й элемент — сколько пар вышек может связать вышка i как ретранслятор.cables=[[0, 1, 2], [1, 2, 3], [1, 3, 4]], step=2 → [0, 1, 0, 0]
Через узел 1 расходятся три ветки. До узла 0 длина 2, до узла 3 — 4, обе кратны 2; до узла 2 длина 3 не подходит. Получается одна пара (0, 3).
cables=[[0, 1, 1], [0, 2, 1], [0, 3, 1]], step=1 → [3, 0, 0, 0]
Звезда с центром 0: любые два листа лежат в разных ветках, это 3 пары. Через лист ничего не проходит.
cables=[[0, 1, 1], [1, 2, 1]], step=2 → [0, 0, 0]
У узла 1 оба соседа на расстоянии 1, а оно не кратно 2. У крайних узлов всего одна ветка.
cables содержит n − 1 кабель и образует деревоcables=[[0, 1, 2], [1, 2, 3], [1, 3, 4]], step=2
[0, 1, 0, 0]
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 95 тестов на сервере, включая скрытые.