47
правок
Изменения
м
→Реализация
===Реализация===
Заполним изначально массив <tex>dp[V][2]</tex> числом числами -1. (<tex>V</tex> {{---}} число вершин)
calculate(v, useRoot):
if dp[v][useRoot] != -1:
return dp[v][useRoot] //вернули уже посчитанное значение dp[vertex][root]
sum = 0
if useRoot == 0: //случай 1: не берем ребра из корня
sum += calculate(u, 1)
dp[v][useRoot] = sum
else: //случай 2: берем какое-то ребро max1 = dp[v][0] //случай 2: берем какое-то ребро
for (для) всех x из множества детей v:
max1 = max(max1, calculate(x, 0) + calculate(vertex, 0) - calculate(x, 1) + w[v,x])
