树形DP POJ2342 基础题

传送门

//MADE BY Y_is_sunshine;
//#include <bits/stdc++.h>
//#include <memory.h>
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <cstdio>
#include <vector>
#include <string>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <math.h>

#define INF 0x3f3f3f3f
#define MAXN 6000

const int mod = 1e9 + 7;

using namespace std;

struct node {
	int to;
	int next;
}edge[MAXN << 1];

int N;
int cnt;
int from[MAXN];
int price[MAXN];
int dp[MAXN][2];

void add(int x, int y) {
	edge[++cnt].next = from[x];
	edge[cnt].to = y;
	from[x] = cnt;
}

void dfs(int u, int fa) {
	for (int i = from[u]; i; i = edge[i].next) {
		int v = edge[i].to;
		if (v == fa)
			continue;
		dfs(v, u);
		dp[u][0] += max(dp[v][0], dp[v][1]);
		dp[u][1] += dp[v][0];
	}
}

int main()
{
	freopen("data.txt", "r", stdin);

	cin >> N;
	for (int i = 1; i <= N; i++)
		scanf("%d", &price[i]);
	int a, b;
	while (cin >> a >> b) {
		if (!a && !b)
			break;
		add(a, b);
		add(b, a);
	}

	for (int i = 1; i <= N; i++)
		dp[i][1] = price[i];
	dfs(1, -1);

	cout << max(dp[1][0], dp[1][1]) << endl;

	freopen("CON", "r", stdin);
	system("pause");
	return 0;
}