自动搬运

查看原文

来自洛谷，原作者为

	QwQcOrZ AFOed | 印刷成文不能代表它们就是真理 | 极东魔术昼寝结社之夏 | The Great Gig In The Sky

搬运于2025-08-24 22:16:05，当前版本为作者最后更新于2021-09-17 20:08:17，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

树形 dp。

思考转移的时候可以考虑开始只有一个点，每次加一棵子树进去，这样思考起来会清晰一点。

由于覆盖一条边的可能是相邻点或者其相邻边连向的点，所以处理时 $i$ 子树内与 $i$ 相邻的边可能未被覆盖，所以需要将其考虑到状态里。

记 $f_{i,j=0/1/2/3/4,k=0/1/2}$ 表示 $i$ 子树内，$j=0$ 表示 $i$ 与 $i$ 的儿子都没有放发射器，$j=1/2$ 分别表示 $i$ 放了 $1$、$2$ 个发射器，$j=3/4$ 分别表示 $i$ 的儿子放了 $1$、$\geq2$ 个发射器，$k$ 表示 $i$ 子树内与其相邻的边还需要的发射器数量。

不需要考虑 $i$ 和 $i$ 儿子都放了发射器的情况，因为这个时候只有 $i$ 上的发射器有用。

转移时，记当前节点为 $u$，加入的儿子为 $v$。

先考虑 $v$ 子树内与 $v$ 相邻的未覆盖边，它们需要 $u$ 放的发射器数量为 $v$ 状态中的 $k$，根据这个条件先判掉不合法的转移。

再考虑 $u$ 与 $v$ 之间的连边：

1. 如果 $u$ 或 $v$ 上有发射器，则此边已被覆盖，直接不管；

2. 否则此边相邻点上的发射器数量为 $u$ 儿子上发射器数量 $+$ $v$ 儿子上发射器数量，这两个都记在 dp 状态中了。根据这个更新 $u$ 状态的 $k$ 值。

还有就是根据 $v$ 上的发射器数量来更新 $u$ 状态 $j,k$ 的值。

具体可以自己画张图思考一下，或者直接看代码

$\texttt{Code Below}$

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int inf;

int read()
{
	int s=0;
	char c=getchar(),lc='+';
	while (c<'0'||'9'<c) lc=c,c=getchar();
	while ('0'<=c&&c<='9') s=s*10+c-'0',c=getchar();
	return lc=='-'?-s:s;
}
void write(int x)
{
	if (x<0) putchar('-'),x=-x;
	if (x<10) putchar(x+'0');
	else write(x/10),putchar(x%10+'0');
}
void print(int x,char c='\n')
{
	write(x);
	putchar(c);
}
struct edge
{
	int to,nxt;
}e[N*2];
int head[N],cnte=0;
void add_edge(int u,int v)
{
	e[++cnte].to=v;
	e[cnte].nxt=head[u];
	head[u]=cnte;
}
int f[N][5][3],g[5][3];
bool trans(int x,int y,int a,int b,int &c,int &d)
{
	c=x,d=y;
	if (b)
	{
		if (x>2) return 0;
		if (x<b) return 0;
	}
	if (1<=a&&a<=2) d=max(d-a,0);
	if (!((1<=a&&a<=2)||(1<=x&&x<=2)))
	{
		int tot=max(a-2,0)+max(x-2,0);
		d=max(d,2-tot);
	}
	if (1<=a&&a<=2&&!(1<=c&&c<=2)) c=min(a+max(c-2,0)+2,4);
	return 1;
}
void dfs(int now,int father)
{
	f[now][0][0]=0;
	f[now][1][0]=1;
	f[now][2][0]=2;
	for (int i=head[now];i;i=e[i].nxt)
	{
		int to=e[i].to,c,d;
		if (to==father) continue;
		dfs(to,now);
		memcpy(g,f[now],sizeof(g));
		memset(f[now],0x3f,sizeof(f[now]));
		for (int x=0;x<=4;x++)
		for (int y=0;y<=2;y++)
		if (g[x][y]<inf)
		for (int a=0;a<=4;a++)
		for (int b=0;b<=2;b++)
		if (f[to][a][b]<inf)
		if (trans(x,y,a,b,c,d))
		f[now][c][d]=min(f[now][c][d],g[x][y]+f[to][a][b]);
	}
}

signed main(signed bangumi,char *ss969[])
{
	(void)bangumi,(void)ss969;
	memset(f,0x3f,sizeof(f));
	inf=f[0][0][0];
	int n=read();
	for (int i=1;i<n;i++)
	{
		int u=read(),v=read();
		add_edge(u,v);
		add_edge(v,u);
	}
	dfs(1,0);
	int ans=inf;
	for (int i=0;i<=4;i++) ans=min(ans,f[1][i][0]);
	print(ans);
	
	return 0;
}