codeforces

2018-09-25  本文已影响7人  _弓长_大人
#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;
}

上一篇 下一篇

猜你喜欢

热点阅读