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}
\]
戳我看代码
void dfs(int u, int fa) {dp[u][0] = 1;for (auto v : g[u]) {if (fa == v) continue;dfs(v, u);rep(j, 0, k - 1) ans += dp[u][j] * dp[v][k - 1 - j];rep(j, 1, k) dp[u][j] += dp[v][j - 1];}
}
最重要的，树上背包！
例题：[CTSC1997] 选课
状态定义
\(dp_{u,i,j}\)表示在 \(u\) 这里，前 \(i\) 棵子树，共计选择 \(j\) 门课，共可以获得的最大贡献。
状态转移
自己先想想，很简单，或者看代码。
戳我看代码
void dfs(int u){for(auto v:graph[u]){dfs(v); // 先递归求出子树的答案}dp[u][0][1] = score[u];for(int i=1;i<=graph[u].size();i++){int v=graph[u][i-1];int siz_v=graph[v].size(); // 标记1for(int j=1;j<=m+1;j++){ // 至少选自己这门课，才可以考虑子树dp[u][i][j]=dp[u][i-1][j]; // 不选 v 子树，直接继承。// 选 v 子树，枚举选多少for(int k=0;k<=m+1;k++) if(j>k){//至少选自己这门课，才可以考虑子树dp[u][i][j]=max(dp[u][i][j],dp[u][i-1][j-k]+dp[v][siz_v][k])}}}
}