Chloe and pleasant prizes

                            Chloe and pleasant prizes

Problem Link

#include <iostream>

#include <vector>

#define pb push_back

using namespace std;

typedef long long int li;

const li N = 2 * 1e5 + 5;

const li inf = 1LL<<60;

vector<li> g[N]; 

li p[N];

li sum[N];

li dp[N];

li n, u, v;

li ans = -inf;

void dfs(int s, int t)

{

    

    dp[s] = -inf;

    sum[s] = p[s];

    for(int i = 0; i < g[s].size(); i++)

    {

        int v = g[s][i];

        if(v == t)

           continue;

        dfs(v, s);

        sum[s] += sum[v];

        if(dp[s] > -inf)ans=max(ans,dp[s]+dp[v]);

        dp[s]=max(dp[s],dp[v]);

    }

    dp[s] = max(dp[s], sum[s]);

}

int main()

{

    cin >> n;

    for(li i = 1; i <= n; i++)

    {

        cin >> p[i];

       

    }

    for(li i = 0; i < n - 1; i++)

    {

        cin >> u >> v;

        g[u].pb(v);

        g[v].pb(u);

    }

    dfs(1, 0);

    if(ans > -inf)

        cout << ans << endl;

    else

        cout << "Impossible\n";

    return 0;

}