没看题解之前 naive 的做法是:
f[u][i]f[u][i]f[u][i] 表示 uuu 的子树内,建 iii 个伐木场时的最小花费。
g[u][i]g[u][i]g[u][i] 表示在 f[u][i]f[u][i]f[u][i] 的条件下还需要向上转移多少木料。
感觉挺对的,转移方程也写出来了: f[u][i]=min(f[u][i−j]+f[v][j]+g[v][j]×w)f[u][i] = \min(f[u][i-j]+f[v][j]+g[v][j]\times w)f[u][i]=min(f[u][i−j]+f[v][j]+g[v][j]×w) 然后找到一个满优的 jjj。 g[u][i]+=g[v][j]g[u][i] += g[v][j]g[u][i]+=g[v][j]。
感觉也像树上背包,但我树上背包学的是一坨*,调不出来。这是我的代码。求大佬帮我看看,可以给报酬,谢谢!