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