F
树形 \(dp\)
状态定义：
\(dp_{u,j,0/1}\)：考虑子树 \(u\) (\(0\) 表示不算入结点 \(u\)，\(1\) 表示算入结点 \(u\))， 选取恰好 \(j\) 条互不重叠的路径，权值和的最大值
\(f_{u,j}\)：考虑子树 \(u\)，选取恰好 \(j\) 条互不重叠的路径，并且其中必须存在一条路径以 \(u\) 为端点，权值和的最大值
状态转移：
前置知识：树形 \(dp\) 在还没开始转移时，子树 \(u\) 中只有结点 \(u\) 自己；在转移过程中，经过从子树 \(v\) 的转移后，子树 \(v\) 合并到子树 \(u\) 中。也就是说子树 \(u\) 在转移过程中是动态扩容的。
\(init:\) \(dp[u][0][0] = dp[u][0][1] = 0\)；\(dp[u][1][1] = f[u][1] = a[u]\)；其他状态均初始化为 \(-INF\)。
\(trans:\)
- 计算 \(dp[u][j][0]\)：由于子树 \(u\) 内未计入结点 \(u\)，因此子树 \(u\) 和子树 \(v\) 之间不会形成新的路径，二者相互独立，分别计入各自部分的路径即可。
- 计算 \(dp[u][j][1]\)：此时子树 \(u\) 内包括点 \(u\)，需要考虑子树 \(u\) 与 子树 \(v\) 之间是否会形成新的路径——显然，只有 子树 \(u\) 内以 \(u\) 为端点的路径 和 子树 \(v\) 内以 \(v\) 为端点的路径 可以合并为一条路径，这恰好可以由 \(f\) 转移过来：
\(\space\space\space\space\space\) 注意上式 \(j1+j2=j-1\)，因为路径合并使得总路径少了一条。
\(\space\space\space\space\space\) 当然还需要考虑没有路径合并时的情况，此时两棵子树独立：
- 计算 \(f[u][j]\)：仍需要分两种情况：
- 以 \(u\) 为端点的路径在原来的子树 \(u\) 中：\[f_{u,j} = max(f_{u,j1} + dp_{v,j2,1})，j1+j2=j \]
- 以 \(u\) 为端点的路径在子树 \(v\) 中：此时 \(u\) 作用于子树 \(v\)，子树 \(u\) 内应不再包括 \(u\)，应从 \(dp_{u,j,0}\) 转移：\[f_{u,j} = max(f_{v,j1} + a_{u} + dp_{u,j2,0})，j1+j2=j \]
\(ans: max_{i=0}^{k}(dp[1][i][1])\)
！需要特别注意：若发现在转移式右侧有正在被转移的对象，则转移前需要将合并子树前的结果复制下来，并从复制下来的结果转移，否则转移时可能会将覆盖后的结果作为转移来源，进而发生错误。推荐 \(dp\) 数组写成 \(vector\) 的形式，以直接赋值的方式复制合并前的 \(dp\) 数组，代码非常简洁。
上述转移一次 \(dfs\) 即可完成，复杂度 \(O(nk^{2})\)。具体细节见代码
code