poj1848 Tree

.....是我多想了。

我想开f[][0~3]，看到百度上的题解都是[0~2]的，我就改了

方程不是特别难想。。

f代表最小代价

f[i][0]是子树有环过i

f[i][1]是子树除了i都成环了

f[i][2]是子树有条链过i(最少2个点,包括i）

转移见代码（有状态了转移很好想）。

/**

 * Problem:POJ1848

 * Author:Shun Yao

 * Time:2013.9.2

 * Result:Accepted

 * Memo:TreeDP

 */

#include <cstdio>

#define MAXN 110

#define inf 1000

long f[MAXN][3];

long min(long x, long y) {

	return x < y ? x : y;

}

class Edge {

public:

	long v;

	Edge *next;

	Edge() {}

	~Edge() {}

	Edge(long V, Edge *ne) : v(V), next(ne) {}

} *g[MAXN];

void add(long x, long y) {

	g[x] = new Edge(y, g[x]);

	g[y] = new Edge(x, g[y]);

}

void dp(long i, long pa) {

	long sum;

	Edge *e;

	sum = 0;

	for (e = g[i]; e; e = e->next)

		if (e->v != pa) {

			dp(e->v, i);

			sum += f[e->v][0];

		}

	f[i][2] = inf;

	f[i][0] = inf;

	f[i][1] = sum;

	if (g[i]->v == pa && !g[i]->next)

		return;

	static long x, y, z;

	x = inf;

	y = inf;

	for (e = g[i]; e; e = e->next)

		if (e->v != pa) {

			f[i][2] = min(f[i][2], f[e->v][1] - f[e->v][0]);

			f[i][2] = min(f[i][2], f[e->v][2] - f[e->v][0]);

			f[i][0] = min(f[i][0], f[e->v][2] - f[e->v][0]);

			z = min(f[e->v][1], f[e->v][2]) - f[e->v][0];

			if (x > z) {

				y = x;

				x = z;

			} else if (y > z)

				y = z;

		}

	f[i][2] += sum;

	if (y < inf)

		f[i][0] = min(f[i][0], x + y);

	f[i][0] += sum + 1;

}

int main() {

	static long n, i, u, v;

#ifndef ONLINE_JUDGE

	freopen("poj1848.in", "r", stdin);

	freopen("poj1848.out", "w", stdout);

#endif

	scanf("%ld", &n);

	for (i = 1; i < n; ++i) {

		scanf("%ld%ld", &u, &v);

		add(u, v);

	}

	dp(1, 0);

	if (f[1][0] >= inf)

		printf("-1");

	else

		printf("%ld", f[1][0]);

	fclose(stdin);

	fclose(stdout);

	return 0;

}