P2279 [HNOI2003] 消防局的设立题解加总结

神奇大自然 發表於 2025-11-12 14:41:00

P2279 [HNOI2003] 消防局的设立题解加总结

<h1 id="正题之前">正题之前</h1>
又是一道抓耳挠腮想了好久的好题， AC 了之后，感觉自己的思想又得到了洗礼 QwQ <s>，第一次写题解，有错望老师见谅</s>
题目传送门
<hr>
<h1 id="思路">思路</h1>
因为题目求的是覆盖树上所有点的所放置最少的消防站数量，因此此题需使用树形 DP 解决
<h2 id="状态申明">状态申明</h2>
因为每个"消防局"能覆盖与它距离不超过 2 的节点，因此 
总共设有5个状态
<ul>
<li>dp 为覆盖到 $x$ 的爷爷（包括父亲）和 $x$ 整棵子树的最少个数；</li>
<li>dp 为覆盖到 $x$ 的父亲和 $x$ 整棵子树的最少个数；</li>
<li>dp 为覆盖 $x$ 整棵子树的最少个数；</li>
<li>dp 为覆盖所有 $x$ 的儿子及其子树的最少个数；</li>
<li>dp 为覆盖所有 $x$ 的孙子及其子树的最少个数；</li>
</ul>
<h2 id="状态转移方程">状态转移方程</h2>
<ul>
<li>dp = 1 $+$ <img src="http://latex.codecogs.com/gif.latex? \tiny \sum" title="\tiny \sum"> dp （ $y$ 为 $x$ 的孩子）</li>
</ul>
<blockquote>
要覆盖到爷爷的话必须选 $x$ ，并贪心地选 $y$ 的第五种状态
</blockquote>
<ul>
<li>dp = min ( dp + <img src="http://latex.codecogs.com/gif.latex? \tiny \sum" title="\tiny \sum">dp )（ $y$ 和 $k$ 皆为 $x$ 的孩子且 $y$ <img src="http://latex.codecogs.com/gif.latex? \tiny \ne" title="\tiny \ne"> $k$ )</li>
</ul>
<blockquote>
$x$ 的儿子中有一个一定覆盖的爷爷，同时覆盖到兄弟（因为 $y$ 一定是选了），其他的儿子只需要覆盖的自己的儿子即可
</blockquote>
<ul>
<li>dp = min ( dp + <img src="http://latex.codecogs.com/gif.latex? \tiny \sum" title="\tiny \sum">dp )（ $y$ 和 $k$ 皆为 $x$ 的孩子且 $y$ <img src="http://latex.codecogs.com/gif.latex? \tiny \ne" title="\tiny \ne"> $k$ )</li>
</ul>
<blockquote>
有一个儿子覆盖到父亲，但无法覆盖到 $y$ 的兄弟，所以其他儿子要覆盖到自己
</blockquote>
<ul>
<li>dp = <img src="http://latex.codecogs.com/gif.latex? \tiny \sum" title="\tiny \sum"> dp （ $y$ 为 $x$ 的孩子）</li>
</ul>
<blockquote>
让每个儿子覆盖到自己
</blockquote>
<ul>
<li>dp = <img src="http://latex.codecogs.com/gif.latex? \tiny \sum" title="\tiny \sum"> dp （ $y$ 为 $x$ 的孩子）</li>
</ul>
<blockquote>
让每个儿子覆盖到自己的儿子
</blockquote>
<h2 id="遍历顺序">遍历顺序</h2>
由叶子节点到根
<h2 id="边界条件">边界条件</h2>
<ul>
<li>叶子节点</li>
</ul>
<blockquote>
dp = dp = dp =1 ; 
dp = dp = 0 ;
</blockquote>
<ul>
<li>非叶子节点</li>
</ul>
<blockquote>
dp = 1 , dp = dp = $\infty$ ; 
dp = dp = 0 ;
</blockquote>
<h2 id="输出答案">输出答案</h2>
dp（根包含自己和所有子树的最小答案）
<h2 id="评估效率">评估效率</h2>
时间复杂度：$O (n)$ $ \ \ \ \$ 空间复杂度：$O (n)$
<h2 id="注意">注意</h2>
因为 dp 的答案包含 dp , dp 的答案包含 dp。同理，因此 dp $\le$ dp $\le$ dp $\le$ dp $\le$ dp , 但如果 dp < dp，因此就该跟新 dp 。
<h1 id="ac代码">AC代码</h1>
<details>
<summary> 点开有惊喜</summary>
<pre><code>#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll INF=1e18;
ll n,y,dp;
vector<ll>t;
void dfs(ll x,ll fa){
ll cnt=0,s2=0,s3=0;
for(auto y:t){
if(y==fa) continue;
dfs(y,x);
s2+=dp;
s3+=dp;
cnt++;
}
if(!cnt){
dp=dp=dp=1;
dp=dp=0;
return;
}
dp=1;dp=dp=INF;
dp=0;dp=0;
for(auto y:t){
if(y==fa) continue;
dp+=dp;
dp=min(dp+s3-dp,dp);
dp=min(dp+s2-dp,dp);
dp+=dp;
dp+=dp;
}
for(int i=1;i<5;i++)
dp=min(dp,dp);
}
int main(){
cin>>n;
for(int i=1;i<n;i++){
cin>>y;
t.push_back(y);
t.push_back(i+1);
}
dfs(1,0);
cout<<dp;
return 0;
}
</code></pre>
</details> 
来源：https://www.cnblogs.com/chenxuan11/p/19127830

頁: [1]

琼殿技术论坛's Archiver

P2279 [HNOI2003] 消防局的设立 题解加总结

P2279 [HNOI2003] 消防局的设立题解加总结