UVA 12452 Plants vs. Zombies HD SP 树形dp（水

题目链接：点击打开链接

题意：

给定n个点的树[0,n)

开始所有边都是无色。

有3种操作：

1、选一个点染其相连的边 花费100

2、选一个点染其相连的2条边 花费175

3、选一个点染其相连的所有边 花费500

问：

染完所有边的最小花费。边可以重复染，点只能被操作一次。

#include <string>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <vector>
template <class T>
inline bool rd(T &ret) {
	char c; int sgn;
	if(c=getchar(),c==EOF) return 0;
	while(c!='-'&&(c<'0'||c>'9')) c=getchar();
	sgn=(c=='-')?-1:1;
	ret=(c=='-')?0:(c-'0');
	while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
	ret*=sgn;
	return 1;
}
template <class T>
inline void pt(T x) {
    if (x <0) {
        putchar('-');
        x = -x;
    }
    if(x>9) pt(x/10);
    putchar(x%10+'0');
}

using namespace std;
typedef long long ll;
const int N = 10100;
const ll inf = 1e10;
struct Edge{
	int to, nex;
}edge[N<<1];
int head[N], edgenum;
void add(int u, int v){
	Edge E = {v, head[u]};
	edge[edgenum] = E;
	head[u] = edgenum++;
}
void init(){memset(head, -1, sizeof head); edgenum = 0;}
int n;
ll dp[N][2];
/*
dp[i][0] : i的父边选了
dp[i][1] : i的父边不选

*/
void up(ll &x, const ll &y){
    if(y<x)x = y;
}
void dfs(int u, int fa){
	dp[u][0] = dp[u][1] = inf;
	bool isleaf = true;
	ll a[3]; memset(a, 0, sizeof a);
	for(int i = head[u]; ~i; i = edge[i].nex){
		int v = edge[i].to; if(v == fa)continue;
		dfs(v, u);
		a[0] += dp[v][0];
		a[1] += dp[v][1];
		a[2] += min(dp[v][0], dp[v][1]);
		isleaf = false;
	}
	if(isleaf)	{dp[u][0] = 100; dp[u][1] = 0;return; }
///////
    up(dp[u][0], a[0]+100);
    up(dp[u][0], a[2]+500);
    up(dp[u][1], a[0]);
	ll b[3]; b[0] = b[1] = inf;
	for(int i = head[u]; ~i; i = edge[i].nex){
		int v = edge[i].to; if(v == fa)continue;
		up(dp[u][0], a[0]-dp[v][0]+dp[v][1] + 175);
		b[2] = -dp[v][0]+dp[v][1];
		sort(b, b+3);
	}
	up(dp[u][1], a[0]+b[0]+b[1]+175);
}
void input(){
	init();
	rd(n);
	for(int i = 1, u, v; i < n; i++){
		rd(u); rd(v);
		add(u, v); add(v, u);
	}
}
int main() {
	int T;scanf("%d", &T);
	while(T--){
		input();
		dfs(0, 0);
	//	for(int i = 0; i < n; i++)printf("%d: %lld %lld\n", i, dp[i][0], dp[i][1]);
		printf("$%lld\n", min(dp[0][0], dp[0][1]));
	}
	return 0;
}
/*
99
10
0 1
0 2
3 2
2 4
3 5
3 6
3 7
3 8
3 9

6
0 1
0 2
0 3
3 4
4 5

7
0 1
1 2
2 3
2 4
2 5
5 6

5
0 1
0 2
0 3
3 4

5
0 1
0 2
0 3
0 4

7
0 1
0 2
0 3
0 4
0 5
0 6

7
0 1
0 2
1 3
3 4
5 2
5 6

*/

UVA 12452 Plants vs. Zombies HD SP 树形dp（水

原文：http://blog.csdn.net/qq574857122/article/details/41528431