RT

• $a$ 点放置了 Wifi 发射器或者 $b$ 点放置了 Wifi 发射器。
• 与 $a$ 点或 $b$ 点直接相邻的点中，至少放置了两个 Wifi 发射器。

第二条是指

1.对于每个与 $a$ 点 或 $b$ 点相邻的点，放置的 Wifi 发射器的和 $\ge 2$

还是2.对于每个与 $a$ 点 放置的 Wifi 发射器的和 $\ge 2$ 或 对于每个与 $b$ 点 放置的 Wifi 发射器的和 $\ge 2$

还是3.对于每个与 $a$ 点 或 $b$ 点相邻的点，存在一个点放置的 Wifi 发射器的数量 $\ge 2$

我是理解成了第一种的，但是只有 36 pts，我认为思路是没问题的，应该是 DP 写错了，但是调了半天没调出来，所以还是先确认一下题意

如果我理解的题意没错，那还劳烦各位大佬帮调

我是设 $f[x][1/2]$ 为点 $x$ 放置 1/2 个 Wifi 的代价，$g[x][0/1/2][0/1/2]$ 为与点 $x$ 相邻的点中有等于或大于等于 0/1/2 个 Wifi 同时其父节点有 0/1/2 个 Wifi 的代价。

#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
#include<iostream>
using namespace std;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
	return x*f;
}
const int MAXN=2e5+10;
int n,f[MAXN][3],g[MAXN][3][3],size[MAXN];
vector <int> v[MAXN];
inline int min(int a=1e9+7,int b=1e9+7,int c=1e9+7,int d=1e9+7,int e=1e9+7,int f=1e9+7,int g=1e9+7,int h=1e9+7)
{
	if(a>b) swap(a,b);if(a>c) swap(a,c);if(a>d) swap(a,d);
	if(a>e) swap(a,e);if(a>f) swap(a,f);if(a>g) swap(a,g);
	if(a>h) swap(a,h);return a;
}
void dfs(int x,int fa=0)
{
	f[x][1]=1,f[x][2]=2,size[x]=1;
	int cnta=0,cntb=0,MINa=MAXN,MIN1=MAXN,MIN2=MAXN;
	for(register int i=0;i<(int)v[x].size();++i)
	{
		int y=v[x][i];if(y==fa) continue;dfs(y,x);size[x]+=size[y];
		f[x][1]+=min(g[y][0][0],g[y][1][0],g[y][1][1],g[y][2][0],g[y][2][1],f[y][1],f[y][2]);
		f[x][2]+=min(g[y][0][0],g[y][1][0],g[y][1][1],g[y][2][0],g[y][2][1],g[y][2][2],f[y][1],f[y][2]);
		g[x][0][0]+=min(g[y][2][0],f[y][1],f[y][2]);
		g[x][1][0]+=min(g[y][2][0],g[y][1][0],f[y][1],f[y][2]);
		g[x][1][1]+=min(g[y][2][0],g[y][1][0],f[y][1],f[y][2]);
		g[x][2][0]+=min(g[y][2][0],g[y][1][0],g[y][0][0],f[y][1],f[y][2]);
		g[x][2][1]+=min(g[y][2][0],g[y][1][0],g[y][0][0],f[y][1],f[y][2]);
		g[x][2][2]+=min(g[y][2][0],g[y][1][0],g[y][0][0],f[y][1],f[y][2]);
		if(min(f[y][1],f[y][2])<=min(g[y][2][0],g[y][1][0])) cnta+=(f[y][2]<f[y][1])?2:1;
		else MINa=min(MINa,min(f[y][1],f[y][2])-min(g[y][2][0],g[y][1][0]));
		if(min(f[y][1],f[y][2])<=min(g[y][2][0],g[y][1][0],g[y][0][0])) cntb+=(f[y][2]<f[y][1])?2:1;
		else
		{
			int num=min(g[y][2][0],g[y][1][0],g[y][0][0]);
			MIN2=min(MIN2,f[y][2]-num,f[y][1]-num+MIN1);
			MIN1=min(MIN1,f[y][1]-num);
		}
	}
	if(cnta==0) g[x][1][0]+=MINa;
	if(cntb==0) g[x][2][0]+=MIN2,g[x][2][1]+=MIN1;
	if(cntb==1) g[x][2][0]+=MIN1;
	if(size[x]-1<1) g[x][1][0]=g[x][2][1]=MAXN;
	if(size[x]-1<2) g[x][2][0]=MAXN;
	return ;
}
int main()
{
	n=read();
	for(register int i=1,a,b;i<n;++i)
	{
		a=read(),b=read();
		v[a].push_back(b),v[b].push_back(a);
	}
	dfs(1);printf("%d\n",min(f[1][1],f[1][2],g[1][0][0],g[1][1][0],g[2][2][0]));
	return 0;
}