独立集

#include <bits/stdc++.h>
using namespace std;
const int N = 5e4 + 5;
int n, d[N], dp[N][2];
vector<int> g[N];
inline void dfs(int u, int fa)
{
	dp[u][0] = 0;
	dp[u][1] = 1;//选点u 
	for(int i = 0; i < g[u].size(); i++){
		int v = g[u][i];
		if(v == fa) continue;
		dfs(v, u);
		dp[u][0] += max(dp[v][0], dp[v][1]);//不选点u，子节点可选可不选 
		dp[u][1] += dp[v][0];//选点u，那么子节点不能再选了 
	}
}
int main()
{
	cin >> n;
	for(int i = 1; i < n; i++){
		int a, b;
		cin >> a >> b;
		g[b].push_back(a);
		g[a].push_back(b);
	}
	dfs(1, -1);//从节点1开始dfs，1相当于根节点 
	cout << max(dp[1][1], dp[1][0]) << "\n";
	return 0;
}

支配集

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n;
const int N = 1e5, inf = 99999999;
int dp[N][3], a[N];
vector<int> g[N];
inline void dfs(int u, int fa)//模板
{
	dp[u][2] = 0;//定义为不要点u加入支配集，点u为根的子树所有节点都被覆盖，但是点u不被任何一个子节点覆盖的情况下，支配集最少节点的个数 
	dp[u][1] = 1;//定义为选择点u加入支配集，并且点u为根的子树所有节点都被覆盖了的情况下，支配集中包含最少的节点个数 
	dp[u][0] = inf;//定义为不要点u加入支配集，点u为根的子树所有节点都被覆盖，并且点u被至少一个子节点覆盖的情况下，支配集最少节点个数
	int sum = 0, ans = inf;
	bool flag = 0;
	for(int i = 0; i < (int)g[u].size(); i++){
		int v = g[u][i];
		if(v == fa) continue;
		dfs(v, u);
		dp[u][1] += min(dp[v][1], min(dp[v][0], dp[v][2]));//点u被选，和子节点无关，累加子节点的三种情况的最小值，随便选 
		sum += min(dp[v][1], dp[v][0]);//累计子节点中已经被覆盖的情况，为dp[u][0]做准备
		dp[u][0] = sum;
		if(dp[v][0] >= dp[v][1]) flag = 1;//表示存在一个子节点已经被选择，可以通过他覆盖节点u
		if(dp[v][0] < dp[v][1]) ans = min(ans, dp[v][1] - dp[v][0]);//保存dp[v][1]和dp[v][0]的差值最小值 
        dp[u][2] += dp[v][0]; //为了得到最小值，我们把差值最小的从dp[v][0]替换为dp[v][1]，强行选择这个子节点，这样点u就可以满足覆盖条件
	}	
	if(!flag && ans != inf) dp[u][0] += ans;
}
signed main()
{
	cin >> n;
	for(int i = 1; i <= n; i++){
		int id, k, m;
		cin >> id >> k >> m;
		a[id] = k;
		for(int j = 1; j <= m; j++){
            int r;
			cin >> r;
			g[id].push_back(r);
			g[r].push_back(id);
		}
	}
	dfs(1, -1);
	cout << min(dp[1][1], dp[1][0]);
	return 0;
}