经典问题系列
覆盖半径\(1\)的最小点覆盖集
\(f[i][0]\) 表示不在此处建信号塔，但\(i\)及其子树都有信号
\(f[i][1]\) 表示在此处建信号塔，但\(i\)及其子树都有信号
\(f[i][2]\) 表示不在在此处建信号塔，但\(i\)子树都有信号，而\(i\)无信号
\(f[p][2]=\sum f[q][0]\)
\(f[p][1]=\sum min(f[q][0],f[q][1],f[q][2])\)
\(f[p][0]=min_q (f[q][1]+\sum_k min(f[k][0],f[k][1]))\)
答案就是 \(min(f[1][0],f[1][1])\)
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1000005;
vector <int> g[N];
int vis[N],f[N][3],t1,t2,t3,n;
void dfs(int p) {
vis[p]=1;
int fa=0;
f[p][1]=1;
for(int i=0;i<g[p].size();i++) {
int q=g[p][i];
if(vis[q]==0) {
dfs(q);
f[p][2]+=f[q][0];
f[p][1]+=min(f[q][0],min(f[q][1],f[q][2]));
}
else fa=q;
}
f[p][0]=1e+16;
for(int i=0;i<g[p].size();i++) {
int q=g[p][i];
if(q!=fa) {
int tmp=f[q][1];
for(int j=0;j<g[p].size();j++) {
int k=g[p][j];
if(k!=fa && k!=q) {
tmp += min(f[k][0],f[k][1]);
}
}
f[p][0]=min(f[p][0],tmp);
}
}
}
signed main() {
scanf("%lld",&n);
for(int i=1;i<n;i++) {
scanf("%lld%lld",&t1,&t2);
g[t1].push_back(t2);
g[t2].push_back(t1);
}
dfs(1);
cout<<min(f[1][0],f[1][1])<<endl;
}