113
правок
Изменения
→Псевдокод
=== Псевдокод ===
<font color = darkgreen>//в основной процедуре вызываем dfs от корня(root), после этого ответ будет хранится в c[root] </font color = darkgreen>
'''function''' dfs(x: '''int'''):
'''for''' (child c : Ch[x]) dfs(childc) a[x] = max(a[x], b[childc] + w[x][childc] - с[childc]) <font color = darkgreen>//по формуле выше, но без b[x](прибавим его один раз в конце) </font color = darkgreen> b[x] += с[childc]
a[x] += b[x] <font color = darkgreen>// так как в a[x] пока что хранится только на сколько мы можем увеличить ответ если будем использовать вершину x</font color = darkgreen>
c[x] = max(a[x], b[x])
== Задача о сумме длин всех путей в дереве ==
