洛谷2633 王后万岁

王后万岁"/>

洛谷2633 王后万岁

题目：=2633
分析：DP
代码：

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
const int Tmax=16005;
int n,data[Tmax],ans=-2147483640;
vector<int> G[Tmax];
int dp(int x,int fa)
{int i,len=G[x].size(),tmp,sum=data[x],to;for(i=0;i<len;i++){to=G[x][i];if(to==fa) continue;tmp=dp(to,x);if(tmp>0) sum+=tmp;}ans=max(ans,sum);return sum;
}
int main()
{int i,u,v;scanf("%d",&n);for(i=1;i<=n;i++)scanf("%d",&data[i]);for(i=1;i<n;i++){scanf("%d%d",&u,&v);G[u].push_back(v);G[v].push_back(u);}ans=max(ans,dp(1,0));printf("%d",ans);return 0;
}