47
правок
Изменения
м
→Псевдокод
===Псевдокод===
calculate(vertex, use_rootuseRoot): if dp[vertex][rootuseRoot] != -1: return dp[vertex][use_rootuseRoot] //вернули уже посчитанное значение dp[vertex][root]
sum = 0
if use_root == 0: //случай 1: не берем ребра из корня
for u in child(vertex):
sum += calculate(u, 1)
dp[vertex][use_rootuseRoot] = sum //выполняем мемоизацию
return sum
max1 = dp[vertex][0]
for x in child(vertex): //случай 2: берем какое-то ребро
max1 = max(max1, calculate(x, 0) + calculate(vertex, 0) - calculate(x, 1) + w[vertex,x])
dp[vertex][use_rootuseRoot] = max1 //выполняем мемоизацию return dp[vertex][use_rootuseRoot]
==Ссылки==
