4199973_ac_79ms_764k.cpp

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

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

using namespace std;

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

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

void dfs(short u, short father)
{
	short 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] = 10001;
		f[u][1] = 1;
		f[u][2] = 0;
		return ;
	}
	short mark = 0;
	short minv = 10001;
	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;
		}
		short 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()
{
	short 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;
}