CF161D Distance in Tree + 树上背包
<h2 id="cf161d-distance-in-tree">CF161D Distance in Tree</h2><h3 id="dp状态定义">DP状态定义</h3>
<p>根据子树位置<span class="math inline">\(+\)</span>路径长度的统计设计状态。</p>
<p><span class="math inline">\(Dp_{u,j}\)</span>表示在以 <span class="math inline">\(u\)</span> 为根的子树中，到 <span class="math inline">\(u\)</span> 的距离恰好为 <span class="math inline">\(j\)</span> 的节点个数。</p>
<h3 id="初始化">初始化</h3>
<p></p><div class="math display">\[dp_{u, 0}=1
\]</div><p></p><h3 id="状态转移方程式">状态转移方程式</h3>
<p>在合并子树时来统计答案</p>
<p></p><div class="math display">\[ans = ans + \sum^k_{j=0}dp_{u,j} \times dp_{j,k-1-j}
\]</div><p></p><p>处理完答案后再合并子树：</p>
<p></p><div class="math display">\[dp_{u,j}=dp_{u,j}\sum^k_{j=1}dp_{v,j-1}
\]</div><p></p><details>
<summary>戳我看代码</summary>
<pre><code>void dfs(int u, int fa) {
dp = 1;
for (auto v : g) {
if (fa == v) continue;
dfs(v, u);
rep(j, 0, k - 1) ans += dp * dp;
rep(j, 1, k) dp += dp;
}
}
</code></pre>
</details>
<h1 id="最重要的树上背包">最重要的，树上背包！</h1>
<h2 id="例题ctsc1997-选课">例题： 选课</h2>
<h3 id="状态定义">状态定义</h3>
<p><span class="math inline">\(dp_{u,i,j}\)</span>表示在 <span class="math inline">\(u\)</span> 这里，前 <span class="math inline">\(i\)</span> 棵子树，共计选择 <span class="math inline">\(j\)</span> 门课，共可以获得的最大贡献。</p>
<h3 id="状态转移">状态转移</h3>
<p>自己先想想，很简单，或者看代码。</p>
<details>
<summary>戳我看代码</summary>
<pre><code>void dfs(int u){
for(auto v:graph){
dfs(v); // 先递归求出子树的答案
}
dp = score;
for(int i=1;i<=graph.size();i++){
int v=graph;
int siz_v=graph.size(); // 标记1
for(int j=1;j<=m+1;j++){ // 至少选自己这门课，才可以考虑子树
dp=dp; // 不选 v 子树，直接继承。
// 选 v 子树，枚举选多少
for(int k=0;k<=m+1;k++) if(j>k){//至少选自己这门课，才可以考虑子树
dp=max(dp,dp+dp)
}
}
}
}
</code></pre>
</details><br><br>
来源：https://www.cnblogs.com/sPERbEETLE/p/19576287
頁:
[1]