4005248_ac_0ms_232k.cpp

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

#include <stdio.h>
#include <vector>
#include <algorithm>
#define inf 0xffff
using namespace std;

int n;
typedef vector <int> VI;
vector <VI> tree;
int fa[101];
int a[101], b[101], c[101];

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

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

	fa[u] = father;
	for (i = 0; i < tree[u].size(); i++)
	{
		if (tree[u][i] == fa[u])
			continue;
		leaf = 0;
		dfs(tree[u][i], u);
	}
	if (leaf)
	{
		a[u] = c[u] = inf;
		b[u] = 0;
		return ;
	}
	b[u] = c[u] = a[u] = 0;
	vector <int> tmp;
	tmp.clear();
	int nmin = inf;
	for (i = 0; i < tree[u].size(); i++)
	{
		int v = tree[u][i];
		if (v == fa[u])
			continue;
		b[u] += a[v];
		tmp.push_back(fmin(b[v], c[v]) - a[v]);
		nmin = fmin(nmin, c[v] - a[v]);
	}
	tmp.push_back(inf);
	sort(tmp.begin(), tmp.end());
	a[u] = b[u] + fmin(tmp[0] + tmp[1], nmin) + 1;
	c[u] = b[u] + tmp[0];
	a[u] = fmin(a[u], inf);
	b[u] = fmin(b[u], inf);
	c[u] = fmin(c[u], inf);
}

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

	scanf("%d", &n);
	tree.resize(n);
	for (i = 1; i < n; i++)
	{
		scanf("%d%d", &u, &v);
		u--;v--;
		tree[u].push_back(v);
		tree[v].push_back(u);
	}
	dfs(0, -1);
	printf("%d\n", a[0] >= inf ? -1 : a[0]);
	return 0;
}