时间限制：0.25s
空间限制：4M
题意：
有n(n<=16000)个小镇，每两个小镇有且仅有一条路径相连。每个小镇有一个收益x（-1000<=x<=1000）.
现在要求,选择一些小镇,满足下面两点要求:
1.选择的小镇都能互相到达,并且路径上的小镇也被选择了.
2.选择的小镇的收益和最大.
输入
一个整数n,接下来n个整数,代表这n个小镇的收益.
接下来n-1行,每行两个整数代表这两个小镇有道路直接相连.
输出
一个整数,代表最大的收益
Sample Input
5
-1 1 3 1 -1
4 1
1 3
1 2
4 5
Sample Output
4
Solution:
先来分析一下题目模型：
有一颗n(n<=16000)个节点的树，每个节点都有一个权值k（-1000<=k<=1000）,
求这颗树的一颗子树,使得子树的所有节点的权值和最大.
假设已经选择了一些点,对于于他相邻的点,求出相邻点的连通块的和的最大值,如果这个值大于0,那么久把这个连通块加入选择.
DFS即可.
参考代码:
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#define INf 16666
#define Maxn 0xfffffff
using namespace std;
vector<int> g[INf];
int val[INf], f[INf];
int n, x, y, tem;
int dfs (int x, int fa) {
f[x] = val[x];
for (int i = 0; i < g[x].size(); i++) {
tem=0;
if (g[x][i] != fa)
tem = dfs (g[x][i], x);
if (tem > 0) f[x] += tem;
}
return f[x];
}
int main() {
scanf ("%d", &n);
for (int i = 1; i <= n; i++) scanf ("%d", &val[i]);
for (int i = 1; i < n; i++) {
scanf ("%d %d", &x, &y);
g[x].push_back (y);
g[y].push_back (x);
}
dfs (1, -1);
int ans = -Maxn;
for (int i = 1; i <=n; i++)
ans = max (ans, f[i]);
printf ("%d", ans);
}