#include<bits/stdc++.h>
using namespace std;
#define MAX 400005
typedef long long ll;
#define inf -1000000005
bool vis[MAX];
ll val[MAX];
ll maxval[MAX];
ll dp[MAX];
//ll minval[MAX];
struct Node{
int v,u,id;
};
int pre[MAX];
Node node[MAX];
int head[MAX];
int cnt=0;
int k;
int top=0;
int fk=0;
ll maxans=0;
ll ans=0;
void init()
{
memset(vis,0,sizeof(vis));
memset(maxval,0,sizeof(vis));
memset(val,0,sizeof(vis));
memset(head,-1,sizeof(head));
cnt=0;
top=0;
}
void add_e(int u,int v)
{
node[cnt].v=v;
node[cnt].u=head[u];
head[u]=cnt++;
}
ll a,b;
ll dfs(int u)
{
vis[u]=1;
maxval[u]=val[u];
for(int i=head[u];i!=-1;i=node[i].u)
{
if(!vis[node[i].v])
{
vis[node[i].v]=1;
maxval[u]=maxval[u]+dfs(node[i].v);
if(dp[u]>inf)
{
ans=max(ans,dp[u]+dp[node[i].v]);
}
dp[u]=max(dp[u],dp[node[i].v]);
}
}
dp[u]=max(dp[u],maxval[u]);
return maxval[u];
}
ll sum=0;
int main()
{
while(~scanf("%d",&k))
{
init();
for(int i=1;i<=k;i++)
{
dp[i]=inf;
}
sum=0;
for(int i=0;i<k;i++)
{
scanf("%lld",&val[i+1]);
}
for(int i=0;i<k-1;i++)
{
scanf("%lld%lld",&a,&b);
add_e(a,b);
add_e(b,a);
}
if(k<3)
{
cout<<"Impossible"<<endl;
}
else
{
ans=inf;
dfs(1);
if(ans==inf)
{
cout<<"Impossible"<<endl;
}
else
{
cout<<ans<<endl;
}
}
}
return 0;
}
网友评论