n вершин с номерами от 0 до n - 1, корень — вершина 0. Рёбра заданы массивом edges, где edges[i] = [a, b] соединяет вершины a и b. В каждой вершине i лежит положительное значение values[i].
Вы можете собрать урожай с любых вершин: значение вершины добавляется к вашему счёту, а сама вершина обнуляется. Каждую вершину можно собрать не больше одного раза.
Дерево должно остаться здоровым: на каждом пути от корня до листа сумма значений после сбора должна быть больше нуля.
Верните наибольший счёт, который можно набрать, не нарушив это условие.edges=[[0, 1], [0, 2], [2, 3]], values=[4, 6, 1, 3] → 10
Оставим нетронутым только корень со значением 4 и соберём остальные вершины: 6 + 1 + 3 = 10. Любой путь от корня к листу начинается с 4, так что дерево остаётся здоровым.
edges=[[0, 1]], values=[5, 2] → 5
Обе вершины забрать нельзя — путь 0 → 1 обнулится. Выгоднее забрать корень (5) и оставить лист со значением 2.
n ≤ 2·10⁴edges.length = n - 1, рёбра образуют деревоa, b < nvalues.length = nvalues[i] ≤ 10⁹edges=[[0, 1], [0, 2], [2, 3]], values=[4, 6, 1, 3]
10
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 41 тест на сервере, включая скрытые.