4199962_ac_63ms_860k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <vector>
#include <stdio.h>
#include <algorithm>

using namespace std;

vector <int> map[10000];
int n;
int f[10000][3];

//f[i][0] 表示以i为根的子树，根不取，所有点都满足条件的最优值
//f[i][1] 表示以i为根的子树，根取，所有点都满足条件的最优值
//f[i][2] 表示以i为根的子树，根不取，除了根之外其他点都满足条件的最优值 (根满足也行不满足也行) 

int min(int a, int b)
{
	return a < b ? a : b;
}

void dfs(int u, int father)
{
	int i, leaf = 1;

	for (i = 0; i < map[u].size(); i++)
	{
		if (map[u][i] == father)
		{
			continue;
		}
		leaf = 0;
		dfs(map[u][i], u);
	}
	if (leaf)
	{
		f[u][0] = 0xffff;
		f[u][1] = 1;
		f[u][2] = 0;
		return ;
	}
	int mark = 0;
	int minv = 0xffff;
	f[u][0] = f[u][2] = 0;f[u][1] = 1;
	for (i = 0; i < map[u].size(); i++)
	{
		if (map[u][i] == father)
		{
			continue;
		}
		int tmp = min(f[map[u][i]][0], f[map[u][i]][1]);
		f[u][2] += tmp;
		f[u][1] += min(f[map[u][i]][2], tmp);
		f[u][0] += tmp;
		if (f[map[u][i]][0] >= f[map[u][i]][1])
		{
			mark = 1;
		}
		if (f[map[u][i]][1] > f[map[u][i]][0] && f[map[u][i]][1] - f[map[u][i]][0] < minv)
		{
			minv = f[map[u][i]][1] - f[map[u][i]][0];
		}
	}
	if (!mark)
	{
		f[u][0] += minv;
	}
}

int main()
{
	int i, u, v;

	scanf("%d", &n);
	for (i = 1; i < n; i++)
	{
		scanf("%d%d", &u, &v);
		u--;v--;
		map[u].push_back(v);
		map[v].push_back(u);
	}
	dfs(0, -1);
	printf("%d\n", min(f[0][0], f[0][1]));
	return 0;
}