CF161D Distance in Tree + 树上背包

CF161D Distance in Tree

DP状态界说

根据子树位置\(+\)路径长度的统计筹划状态。
\(Dp_{u,j}\)表现在以 \(u\) 为根的子树中，到 \(u\) 的间隔恰恰为 \(j\) 的节点个数。
初始化


\[dp_{u, 0}=1\]
状态转移方程式

在归并子树时来统计答案

\[ans = ans + \sum^k_{j=0}dp_{u,j} \times dp_{j,k-1-j} \]
处置惩罚完答案后再归并子树：

\[dp_{u,j}=dp_{u,j}\sum^k_{j=1}dp_{v,j-1}\]
戳我看代码

1. void dfs(int u, int fa) {
2.         dp[u][0] = 1;
3.         for (auto v : g[u]) {
4.                 if (fa == v) continue;
5.                 dfs(v, u);
6.                 rep(j, 0, k - 1) ans += dp[u][j] * dp[v][k - 1 - j];
7.                 rep(j, 1, k) dp[u][j] += dp[v][j - 1];
8.         }
9. }

复制代码

最紧张的，树上背包！

例题：[CTSC1997] 选课

状态界说

\(dp_{u,i,j}\)表现在 \(u\) 这里，前 \(i\) 棵子树，共计选择 \(j\) 门课，共可以得到的最大贡献。
状态转移

本身先想想，很简单，大概看代码。
戳我看代码[code]void dfs(int u){        for(auto v:graph){                dfs(v); // 先递归求出子树的答案        }                dp[0][1] = score;        for(int i=1;i