给出一个树，有 $N$ 个结点，结点编号从 $1$ 至 $N$。

假如在第 $i$ 个结点建立一个信号塔，那么与第 $i$ 个结点有边相连的结点就能接受到信号，

当然第 $i$ 个结点本身也能接受到信号。

问题是：至少要在多少个结点建立信号塔，才能使得所有的结点都能接收到信息。

这题跟这题有异曲同工之妙，可是做法完全不一样，如果按照这一题,这份程序是可以过的（不用细看）

#include<bits/stdc++.h>
using namespace std;
long long n,a,b;
long long f[1000005][2];
vector<long long>tree[1000005]; 
void dfs(long long x,long long y)
{
	f[x][1]=1;
	for(int i=0;i<tree[x].size();i++)
	{
		if(tree[x][i]!=y)
		{
			dfs(tree[x][i],x);
			f[x][0]+=f[tree[x][i]][1];
			f[x][1]+=min(f[tree[x][i]][1],f[tree[x][i]][0]);
		}
	}
} 
int main(){
	cin>>n;
	for(int i=1;i<n;i++)
	{
		cin>>a>>b;
		tree[a].push_back(b);
		tree[b].push_back(a);
	} 
	dfs(1,-1);
	cout<<min(f[1][0],f[1][1]);
	return 0;
}

但是只有二十分，看了老师的题解之后打出下面这份代码

#include<bits/stdc++.h>
using namespace std;
long long n,a,b;
long long f[1000005][3]; 
vector<long long>tree[1000005]; 
void dfs(long long x,long long y)
{
	if(tree[x].size()==0 && x!=1)
	{
		f[x][1]=1;
		f[x][0]=0;
		f[x][2]=1e8;
		return;
	}
	f[x][1]=1,f[x][2]=1e8;
	long long s=0,minx=1e8;
	bool small=false;
	for(int i=0;i<tree[x].size();i++)
	{
		if(tree[x][i]!=y)
		{
			dfs(tree[x][i],x);
			f[x][1]+=min(f[tree[x][i]][1],min(f[tree[x][i]][0],f[tree[x][i]][2]));
			f[x][0]+=min(f[tree[x][i]][1],f[tree[x][i]][2]);
			f[x][2]+=min(f[tree[x][i]][1],f[tree[x][i]][2]);
			if(f[x][1]<=min(f[tree[x][i]][1],f[tree[x][i]][2])) small=true;
			else
			minx=min(minx,f[tree[x][i]][1]-min(f[tree[x][i]][1],f[tree[x][i]][2]));
		}
	}
	if(small==false) f[x][2]+=minx;
} 
int main(){
	cin>>n;
	for(int i=1;i<n;i++)
	{
		cin>>a>>b;
		tree[a].push_back(b);
		tree[b].push_back(a);
	} 
	dfs(1,-1);
	cout<<min(f[1][0],min(f[1][1],f[1][2]));
	return 0;
}

也是只有二十分，求修改