时间限制：0.25s

空间限制：4M

题意：

有n(n<=16000)个小镇，每两个小镇有且仅有一条路径相连。每个小镇有一个收益x（-1000<=x<=1000）.    现在要求,选择一些小镇,满足下面两点要求:    1.选择的小镇都能互相到达,并且路径上的小镇也被选择了.    2.选择的小镇的收益和最大.

输入

一个整数n,接下来n个整数,代表这n个小镇的收益.   接下来n-1行,每行两个整数代表这两个小镇有道路直接相连.

输出

一个整数,代表最大的收益

Sample Input

5-1 1 3 1 -14 11 31 24 5

Sample Output

4

 

 

 

 

---

 

Solution:

                先来分析一下题目模型：

 

             有一颗n(n<=16000)个节点的树，每个节点都有一个权值k（-1000<=k<=1000）,

 

             求这颗树的一颗子树,使得子树的所有节点的权值和最大.

 

             假设已经选择了一些点,对于于他相邻的点,求出相邻点的连通块的和的最大值,如果这个值大于0,那么久把这个连通块加入选择.

             DFS即可.

 

参考代码:

 

 

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #define INf 16666#define Maxn 0xfffffffusing namespace std;vector
         
           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);}