细节
题意
给你一棵无向树，问你最少用多少个点可以覆盖掉所有其他的点。 • （一个点被盖，它自己和与它相邻的点都算被覆盖）
思路
状态: 选他，选他儿子，选他父亲都对子树答案有影响。
设:
dp[i][0]：选点i，并且以点i为根的子树都被覆盖了。
dp[i][1]：不选点i，i被其儿子覆盖
dp[i][2]：不选点i，被其父亲覆盖（儿子可选可不选）
状态转移方程: ( u为儿子，i为当前点）
dp[i][0]=1+Σmin(dp[u][0],dp[u][1],dp[u][2])
dp[i][2]=Σ(dp[u][1],dp[u][0])
对于dp[i][1]的讨论稍微复杂一点——他的所有儿子里面必须有一个取dp[u][1]，且他的儿子不存在dp[u][2]。
也就是说对于所有i的儿子，若每一个儿子的都dp[u][1] < dp[u][0]。则只需要让结果dp[i][1]加上min(dp[y][0]-dp[y][1])即可。
#include <iostream> #include <cmath> #include <cstdio> #include <cstring> #include <string> #include <map> #include <iomanip> #include <algorithm> #include <queue> #include <stack> #include <set> #include <vector> // #include <bits/stdc++.h> #define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define sp ' ' #define endl ' ' #define FOR(i,a,b) for( int i = a;i <= b;++i) #define bug cout<<"--------------"<<endl #define P pair<int, int> #define fi first #define se second #define pb(x) push_back(x) #define ppb() pop_back() #define mp(a,b) make_pair(a,b) #define ms(v,x) memset(v,x,sizeof(v)) #define rep(i,a,b) for(int i=a;i<=b;i++) #define repd(i,a,b) for(int i=a;i>=b;i--) #define sca3(a,b,c) scanf("%d %d %d",&(a),&(b),&(c)) #define sca2(a,b) scanf("%d %d",&(a),&(b)) #define sca(a) scanf("%d",&(a)); #define sca3ll(a,b,c) scanf("%lld %lld %lld",&(a),&(b),&(c)) #define sca2ll(a,b) scanf("%lld %lld",&(a),&(b)) #define scall(a) scanf("%lld",&(a)); using namespace std; typedef long long ll; ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} ll lcm(ll a,ll b){return a/gcd(a,b)*b;} ll powmod(ll a, ll b, ll mod){ll sum = 1;while (b) {if (b & 1) {sum = (sum * a) % mod;b--;}b /= 2;a = a * a % mod;}return sum;} const double Pi = acos(-1.0); const double epsilon = Pi/180.0; const int maxn = 2e5+100; std::vector<int> e[maxn]; int n; //0:选择。1：不选择，被儿子覆盖。2：不选择，没被儿子覆盖(准备被父亲覆盖) int dp[maxn][5]; int h[maxn]; int ans1 = 0,ans2 = 0; void dfs(int x,int fa) { dp[x][0] = 1,dp[x][1] = dp[x][2] = 0; int cha = 999999,flag = 0; for(auto y : e[x]){ if(y == fa) continue; dfs(y,x); dp[x][2] += min(dp[y][1],dp[y][0]); dp[x][0] += min(min(dp[y][0],dp[y][1]),dp[y][2]); //儿子一定要有一个放的，但是不必要是所有都是放的。 dp[x][1] += min(dp[y][0],dp[y][1]); if(dp[y][1] < dp[y][0]){ cha = min(cha,dp[y][0]-dp[y][1]); } else flag = 1; } if(flag == 0) dp[x][1] += cha; } int main() { //freopen("input.txt", "r", stdin); while(scanf("%d",&n) != EOF){ rep(i,1,n){ e[i].clear(); } ans1 = 1e6,ans2 = 1e6; rep(i,1,n){ dp[i][1] = 1e5; dp[i][0] = 1e5; } rep(i,1,n-1){ int x,y; sca2(x,y); e[x].pb(y); e[y].pb(x); } dfs(1,0); printf("%d ",min(dp[1][1],dp[1][0])); } }