南阳市理工OJ 697 The Weight of Tree 树上的最大块

南阳理工OJ 697 The Weight of Tree 树上的最大块

连接：http://acm.nyist.net/JudgeOnline/problem.php?pid=697

?

The Weight of Tree时间限制：3000?ms ?|? 内存限制：65535?KB难度：4?

描述

456 has a tree of n nodes, each node is assigned with an integer number. Now 456 wants to select a subtree, such that the sum of all integers on the nodes of the subtree is maxmized. Can you help him???

输入

On the first line of the input is an integer T, and then T cases follows. Each case begins with a positive integer n(1 <= n <= 10^5), then n numbers Wi(-1000 <= Wi <= 1000),Wi for the number on the ith node. Then n - 1 lines follows, each line contains two numbers a, b(1 <= a, b <= n)indicate that there is a edge between node a and b.

输出

For each test case, output one integer on a line, the maximized sum can be achieved by selecting a subtree.?

样例输入

31525 -51 25-2 -3 7 -1 41 22 33 42 5

样例输出

558

?

#include<cstdio>#include<cstring>#include<vector>#define inf 1<<30using namespace std;vector<int>link[100010];bool mask[100010];int w[100010];int maxn,n;int dfs(int a){       int term,res=0;       mask[a]=1;       for(int i=0;i<link[a].size();i++)if(mask[link[a][i]]==0)       {              term=dfs(link[a][i]);              if(term<0)continue;              res+=term;       }       if(res+w[a]>maxn)maxn=res+w[a];       return res+w[a];}int main(){     //  freopen("in.txt","r",stdin);int T;scanf("%d",&T);while(T--){       memset(mask,0,sizeof(mask));       scanf("%d",&n);       for(int i=1;i<=n;i++)link[i].clear();       for(int i=1;i<=n;i++)scanf("%d",&w[i]);       for(int i=1;i<n;i++)       {              int a,b;              scanf("%d%d",&a,&b);              link[a].push_back(b);              link[b].push_back(a);       }       maxn=-inf;       dfs(1);       printf("%d\n",maxn);}return 0;}

?

?

?

?

?

?

?

?

?