自动搬运

查看原文

来自洛谷，原作者为

	xieyikai2333 此时此刻的光辉，盼君勿忘。

搬运于2025-08-24 22:40:31，当前版本为作者最后更新于2022-10-23 21:09:38，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

• 题目传送门

闲话

• 赛时爆肝 T2，结果 T2 是个紫的没打出来，然后这题没时间了，打了个 $20$ 分的暴力滚蛋了。

解题思路

• 显然，我们先进行操作 1 再进行操作 2 一定不劣，否则操作 2 连上去的边可能又被炸掉。

• 考虑把森林炸成若干链，然后连起来，显然如果我们炸了 $x$ 条边，那么操作 2 的次数可以表示为 $(n-1)-(m-x)$。于是我们只要使炸掉的边数（$x$）+炸掉的点数（操作 1 的次数）最小即可。

• 考虑对于每个无根树随便取个根进行树形DP。

状态设计

• 设 $dp_{i,0/1/2}$ 表示 $i$ 的子树已经被炸成若干链了且 $\begin{cases} \text{这个点被炸了} &0\\ \text{这个点没有被炸，它的儿子有 1 个连着它} &1\\ \text{这个点没有被炸，它的儿子有 2 个连着它} &2 \end{cases}$

状态转移

• 约定：记 $son_u$ 为点 $u$ 的儿子集合，$d_u$ 为点 $u$ 的度数，$FIR_{sth}$ 是一类数中的最大值，$SEC_{sth}$ 是一类数中的次大值。

• 对于状态 $0$：

  • 转移方程：$$dp_{u,0}=\sum_{v \in son_{u}} \min\{dp_{v,0}-1,dp_{v,2}\}+d_{u}+1 $$
  • 解释说明：
    • 如果一个点被炸掉，那么它的子树无论何种情况都可以转移。
    • 之所以 $dp_{v,0}$ 要减去 $1$ 是因为如果 $u$ 和 $v$ 都炸它们之间的边被重复计算了。
    • 之所以不用考虑 $dp_{v,1}$，是因为 $dp_{v,1}$ 一定大于 $dp_{v,2}$，原因由后面会给出的 $dp_{v,2}$ 的转移方程可知。
    • 加上 $d_{u}$ 是因为又炸了 $d_{u}$ 条边，加上 $1$ 是因为又炸了一个点

• 对于状态 $1$：

  • 转移方程：$$dp_{u,1}=(\sum_{v \in son_{u}} dp_{v,0})-\max\{0,FIR_{v \in son_{u}}(dp_{v,0}-dp_{v,1})\} $$
  • 解释说明：
    • 由定义，$u$ 的儿子最多有一个不被炸，所以最多有一个儿子状态可以是 $1$ 其他都必须被炸。

• 对于状态 $2$：

  • 转移方程：$$dp_{u,2}=dp_{i,1}-\max\{0,SEC_{v \in son_{u}}(dp_{v,0}-dp_{v,1})\} $$
  • 解释说明：
    • 由定义，$u$ 的儿子最多有两个不被炸。在有一个不被炸的基础上再减去第二大的即可。
  • 由转移方程可知，$dp_{u,2} \lt dp_{u,1}$ 显然成立。

最终答案

• 约定：$ANS$ 是最终答案，$root$ 是每棵树的根节点组成的集合。

至于为什么不用管 $dp_{u,1}$，不用我多说了吧？

代码实现

好像没什么要注意的细节。。。

AC 代码：

#include <bits/stdc++.h>
using namespace std;
const int N=2e6+5;
int dp[N][3];
bool vis[N];
vector<int> nodes[N];
void dfs(int u)
{
	vis[u]=true;
	int fir=0,sec=0;
	for(int v:nodes[u])
	{
		if(vis[v])continue;
		dfs(v);
		int delta=dp[v][0]-dp[v][1];
		if(delta>fir)sec=fir,fir=delta;
		else if(delta>sec)sec=delta;
		dp[u][0]+=min(dp[v][0]-1,dp[v][2]);
		dp[u][1]+=dp[v][0];
	}
	dp[u][0]+=nodes[u].size()+1;
	dp[u][1]-=fir;
	dp[u][2]=dp[u][1]-sec;
	return;
}
int main()
{
	int n,m;
	scanf("%d %d",&n,&m);
	int ans=(n-1)-m;
	for(int i=1;i<=m;i++)
	{
		int u,v;
		scanf("%d %d",&u,&v);
		nodes[u].push_back(v);
		nodes[v].push_back(u);
	}
	for(int i=1;i<=n;i++)if(!vis[i])dfs(i),ans+=min(dp[i][0],dp[i][2]);
	printf("%d",ans);
	return 0;
}