题意:n-1条边,每个点能被相邻的点控制台覆盖,问最少将多少个点设为控制台可以覆盖所有点,
树型dp:dp[x][0]表示x自己是控制台,dp[x][1]表示x的儿子是控制台,dp[x][2]表示父亲是控制台,转移见代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 10005;
vector<int>g[maxn];
int dp[maxn<<1][3];
void dfs(int u, int fa){int mi = 2e9;dp[u][0]=1;for(auto v:g[u]){// cout<<u<<" "<<v<<endl;if(v==fa)continue;dfs(v,u);dp[u][0]+=min(dp[v][0],min(dp[v][1],dp[v][2]));dp[u][2]+=min(dp[v][1],dp[v][0]);if(dp[v][0]-min(dp[v][0],dp[v][1]) < mi) {mi = dp[v][0]-min(dp[v][0],dp[v][1]);}}dp[u][1] = dp[u][2] + mi; }
int main()
{int n;cin>>n;for(int i=1;i<n;i++){int x,y;cin>>x>>y;g[x].push_back(y),g[y].push_back(x);}dfs(1,0);cout<<min(dp[1][0],dp[1][1])<<endl;
}