1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52
|
#include <cstdlib> #include <algorithm> #include <cstring> #include <cctype> #define INF 2000000000 using namespace std; typedef long long ll; int n,at[100005],to[100005],_next[100005],cnt=0; bool vis[100005]; ll val[100005],dp[100005]; int (){ int f=1,x=0;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();} while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar(); return f*x; } void dfs(int cur){ dp[cur]=val[cur]; for(int i=at[cur];i!=-1;i=_next[i]){ if(!vis[to[i]]){ vis[to[i]]=1,dfs(to[i]); if(dp[to[i]]>0)dp[cur]+=dp[to[i]]; } } } void init(){ n=read(); memset(at,-1,sizeof(at)); int u,v; for(int i=1;i<=n;i++) val[i]=read(); for(int i=1;i<n;i++){ u=read(),v=read(); to[cnt]=v,_next[cnt]=at[u],at[u]=cnt++; to[cnt]=u,_next[cnt]=at[v],at[v]=cnt++; } } void solve(){ ll ans=-INF; ans*=2ll; vis[1]=1,dfs(1); for(int i=1;i<=n;i++) ans=max(ans,dp[i]); printf("%lldn",ans); } int main(){ init(); solve(); return 0; }
|
近期评论