n вершин с номерами от 0 до n - 1; рёбра заданы списком edges, где edges[i] = [a, b]. У каждой вершины есть вес values[i], а ещё дано число k. Сумма всех весов делится на k.
Можно удалить любое множество рёбер (в том числе ни одного). Дерево распадётся на части, и вес части — сумма весов её вершин. Разрез хороший, если вес каждой части делится на k.
Верните наибольшее число частей среди всех хороших разрезов.n=4, edges=[[0, 1], [1, 2], [1, 3]], values=[2, 4, 3, 5], k=7 → 1
Общий вес 14. Если удалить ребро 1–3, получатся части весом 5 и 9; ребро 1–2 — 3 и 11; ребро 0–1 — 2 и 12. Ни одна не делится на 7, поэтому дерево остаётся целым: одна часть.
n=5, edges=[[0, 1], [0, 2], [2, 3], [2, 4]], values=[1, 2, 3, 4, 2], k=3 → 2
Отрезать вершину 3 или 4 нельзя: веса 4 и 2 не делятся на 3. Если удалить ребро 0–2, получатся части {2, 3, 4} весом 9 и {0, 1} весом 3. Третью часть выделить не удаётся, ответ 2.
n=1, edges=[], values=[0], k=4 → 1
values делится на kn=4, edges=[[0, 1], [1, 2], [1, 3]], values=[2, 4, 3, 5], k=7
1
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 70 тестов на сервере, включая скрытые.