樹(shù)上背包

09 年論文現(xiàn)在才學(xué)也是沒(méi)救了。

對(duì)于重量為 \(1\) 的，直接每次枚舉 size 就可以做到 \(n^2\)，證明考慮一個(gè)點(diǎn)對(duì)只會(huì)在 lca 出有一個(gè)貢獻(xiàn)。

考慮重量是 \(v_i\)，定義 \(v_i\) 的上界是 \(V\)。

暴力做是 \(nV^2\) 的，實(shí)在是不優(yōu)美。

考慮更改更新順序?yàn)閺捻數(shù)降卓梢宰龅?\(nV\)，具體實(shí)現(xiàn)有兩種。

考慮推到 dfs 序上，設(shè) \(dp_{i,j}\) 表示當(dāng)前到 \(i\) 點(diǎn)，重量是 \(j\)，轉(zhuǎn)移考慮刷表，枚舉這個(gè)點(diǎn)選不選考慮貢獻(xiàn)到 \(i + 1\) 或者 \(i + sz\)（這個(gè)點(diǎn)不選不能選子樹(shù)）。

也可以不用 dfs 序，考慮依次做每個(gè)兒子，最后和自己取 max。

缺點(diǎn)是空間復(fù)雜度沒(méi)在壓了。