判掉 k=1，此时答案为 ∑a；将 bi 对 ai 取 min，同时以 0 为树根且不标记，避免讨论。考虑标记点形态，k=2 时标记 u 点后可向下拓展到子节点，但是需要清除 u 点标记才能接着向下，最终能覆盖毛毛虫形状内的点。定义单点是 1 合法的，对于 i>1，定义 u 子树 i 合法当且仅当存在一个儿子 i 合法， 且其他儿子均 (i−1) 合法，这也能解释 2 合法的形状。
于是对于弱化版，设 fu,i 表示 u 子树内关键点均被标记过，且从 u 开始的拓展过程 i 合法的最小代价。状态不考虑 u 点代价，因为其取值受父亲影响。另外令 fu,0 表示 u 不选时的最小代价。转移为 fu,1=fu,0=∑min(fv,k+av,fv,0)，对于 i>1，有 fu,i=min(fv,i+bv+∑t=vmin(ft,i−1+bt,ft,k+at,ft,0))，只需先对第二个式子求和，再找最优差值更新即可。最后若 u 必须被标记，将 fu,0 赋为正无穷，复杂度 O(nk)。
对于原题，同一个点可被学习多次，即可以从 u 拓展到 v，在 v 拓展的过程中扔掉 u，之后需要标记 v 或其他子节点时再把 u 标记回来。据此设 fu,i,j 表示考虑 u 子树，用到了至多 i 的空间，过程中 u 的子节点拓展需要u 点标记 j 次的最小花费。与上面相同，状态不考虑 u 点代价，这会在父亲节点上决策。
这个状态在定义什么？其包含子树内其他点的标记次数和方式，记录过程中的最大空间消耗和 u用于拓展的标记次数，以便向上转移。由于空间越大越可操作，fu,i,j 随 i 增大单调不增。另外 fu,i,0 并非不标记 u，而是已经考虑的过程没有用 u 拓展，还没有因此标记过 u。最终 fu,i,0 的值是无意义的，事实上代表的是 i′<i 的 fu,i′,y，该状态也不能转移给父亲。至于真的不标记，再设 gu 表示 u 不用于拓展时子树内最小代价，此时子树内其他拓展过程均可使用 k 的空间，不用记录。
由于从某点开始同时向多个子树拓展不优，可以依次处理每个子树，这样可用空间更大。于是可依次将每个子树 v 的信息拼到 u 上。具体地，新拼上一个子树 v 时，有以下几种转移（tv 表示 v 是否需要标记；均有限制 i≥2,j≥0,y≥1）：
v 从 u 拓展来，且拓展过程中一直保留 u，v 标记 y 次：fu,i,j+fv,i−1,y+ybv→fu,i,j′。
v 从 u 拓展来，且 v 不用于向下拓展：fu,i,j+gv+tvbv→fu,i,j′。
v 部分从 u 拓展来，过程中扔掉 u，v 标记 y 次，其中 x 次从 u 拓展：fu,i,j+fv,i,y+xbv+(y−x)av→fu,i,j+x′，有限制 0≤x≤y。
v 不从 u 拓展，标记 y 次：fu,i,j+fv,k,y+yav→fu,i,j′；v 不标记代价为 gv+tvav，不如 2 优。
u 不向下拓展，v 标记 y 次：gu+fv,k,y+yav→gu′；v 不标记：gu+gv+tvav→gu′。
最难理解的可能是转移 3，即 v 用了全部的 i 空间，此时每次从 u 拓展都要重新标记 u。这里状态第三维记录的是用于拓展的标记次数，理解了这一转移大概就能理解状态设计的方式了。
原题