本文共 1335 字，大约阅读时间需要 4 分钟。

观察发现一定是从$1$连出来的边最划算

而且连到一个点之后,这个点周围的所有点都是满足要求的.

定义$f[u][1]$为和$1$有连边

$f[u][2]$为通过父亲到$1$

$f[u][3]$为通过儿子到$1$

那么$f[u][1]=\sum _{v}min(f[v][1],f[v][2],f[v][3])$

那么$f[u][2]=\sum _{v}min(f[v][1],f[v][3])$

$f[u][3]=f[u][2]$

但是如果$u$的儿子没有一个和$1$有边,还需要选一个儿子和$1$相连…

#include 
   
    using namespace std;const int maxn = 4e5+10;struct edge{
   	int to,nxt;}d[maxn]; int head[maxn],cnt=1;void add(int u,int v){
   	d[++cnt]=(edge){
   v,head[u]},head[u] = cnt;}int n,f[maxn][3],ans;//1表示直接相连//2表示经过父亲再到自己//3表示经过儿子再到自己 void dfs(int u,int fa,int dep){
   	if( dep>=2 )	f[u][1] =1;	int minn = 1e9;	for(int i=head[u];i;i=d[i].nxt )	{
   		int v = d[i].to;		if( v==fa )	continue;		dfs(v,u,dep+1);		f[u][1] += min( {
   f[v][1],f[v][2],f[v][3]} );		f[u][2] += min( f[v][1],f[v][3] );		minn = min( minn,f[v][1]-f[v][3] );	}	f[u][3] = f[u][2]+max(0,minn);}int main(){
   	cin >> n;	for(int i=1;i
    
     > l >> r;		add(l,r); add(r,l);	}	dfs(1,0,0);	for(int i=head[1];i;i=d[i].nxt )		ans += f[d[i].to][1];	cout << ans;}
    
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/110203203 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！