n вершин с номерами от 0 до n − 1, подвешенное за вершину 0. Рёбра заданы списком edges, где [a, b] — ребро между a и b. У каждой вершины i есть ненулевое целое значение values[i].
В каждую вершину кладут монеты по правилу:
- если в её поддереве (сама вершина и все её потомки) меньше трёх вершин, кладут 1 монету;
- иначе берут три разные вершины поддерева с наибольшим произведением значений и кладут столько монет, каково это произведение, а если оно отрицательное — 0 монет.
Верните массив длины n, где i-й элемент — число монет в вершине i.edges=[[0, 1], [0, 2], [0, 3]], values=[2, -5, 3, -4] → [60, 1, 1, 1]
В поддереве корня все четыре вершины; лучшая тройка — (-5)·(-4)·3 = 60. Остальные вершины — листья, им по 1 монете.
edges=[[0, 1], [1, 2], [1, 3]], values=[7, 1, 2, -6] → [14, 0, 1, 1]
Поддерево вершины 1 — значения 1, 2, -6: единственное произведение -12 отрицательно, поэтому 0. Для корня лучшая тройка 7·2·1 = 14.
edges=[[1, 0]], values=[-3, 8] → [1, 1]
В обоих поддеревьях меньше трёх вершин.
len(edges) == n − 1, 0 ≤ a, b < nedges задаёт деревоedges=[[0, 1], [0, 2], [0, 3]], values=[2, -5, 3, -4]
[60, 1, 1, 1]
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 43 теста на сервере, включая скрытые.