30分求调...
查看原帖
30分求调...
708102
bijhla楼主2023/7/31 11:50
#include<bits/stdc++.h>
using namespace std;
const int N = 2e4 + 10;
int n, f[N][3], t = 9999999;
vector <int> g[N];
/*
dp[u][0]表示我不选,儿子选 
dp[u][1]表示我不选,父亲选 
dp[u][2]表示我选 
*/
void dfs (int u, int father)
{
	t = 9999999;
	for (int i = 0; i < g[u].size (); i++)
	{
		int v = g[u][i];
		if (v == father)
		{
			continue;
		}
		dfs (v, u);
		f[u][0] += min (f[v][0], f[v][2]);
		t = min (t, f[v][2] - min(f[v][2], f[v][0])); 
		f[u][1] += min (f[v][2], f[v][0]);
		f[u][2] += min (f[v][1], min (f[v][0], f[v][2]));
	}
	f[u][0] += t;
	return;
}
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);
	}
	for (int i = 1; i <= n; i++)
	{
		f[i][0] = f[i][1] = 0;
		f[i][2] = 1;
	}
	dfs (1, 0);
	cout << min (f[1][0], f[1][2]);
 	return 0;
}


2023/7/31 11:50
加载中...