competitive-programming/384D.cpp at master · nishanthta/competitive-programming · GitHub

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <iostream>
#include <algorithm>
#include <limits>
#include <vector>
#include <map>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <set>
#define vi vector<long long>
#define vvi vector< vector<long long> >
#define ll long long
#define mp make_pair
#define si map<long long,long long>::iterator
#define rep(a,b,c) for(ll c = a;c <= b;c++)
using namespace std;

ll a[200005],b[200005] = {},m = -1000000005;

ll f = 1,pf = 0;

bool marked[200005] = {};

vector<vector<ll> > v;

void dfs(ll u,ll pv){
	marked[u] = 1;
	if(u == 1 && v[u].size() == 1){
		dfs(v[u][0],u);
		b[u] = b[u] + b[v[u][0]];
	}
	if((v[u].size() == 2) && u != f){
		b[u] = a[u];
		return;
	}
	else if(v[u].size() == 2 && u == f){
		if(v[u][0] == pf){
			dfs(v[u][1],u);
			b[u] = a[u] + b[v[u][1]];
		}
		else{
			dfs(v[u][0],u);
			b[u] = a[u] + b[v[u][0]];
		}
	}
	b[u] = a[u];
	rep(0,v[u].size() - 1,i){
		if(v[u][i] != pv && !marked[v[u][i]]){
			dfs(v[u][i],u);
			b[u] += b[v[u][i]];
		}
	}
}

void calc(ll u,ll pv){
	if(v[u].size() == 1){
		m = max(m,b[u]);
		return;
	}
	m = max(m,b[u]);
	rep(0,v[u].size() - 1,i){
		if(v[u][i] != pv){
			calc(v[u][i],u);
		}
	}
}


int main(){
	ll n; cin >> n;
	if(n == 1){
		ll tmp; cin >> tmp;
		cout << "Impossible";
		return 0;
	}
	rep(1,n,i){
		cin >> a[i];
		vector<ll> t;
		v.push_back(t);
	}
	vector<ll> t;
	v.push_back(t);
	v.push_back(t);
	rep(1,n - 1,i){
		ll x,y; cin >> x >> y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	vector<ll> val;
	bool poss = 0;
	if(v[1].size() == 1){
		while(v[f].size() <= 2){
			if(f == 1 && v[f].size() == 1){
				pf = f;
				f = v[f][0];
			}
			else if(v[f].size() == 1){
				poss = 1;
				break;
			}
			else{
				if(v[f][0] == pf){
					pf = f;
					f = v[f][1];
				}
				else{
					pf = f;
					f = v[f][0];
				}
			}
		}
	}
	dfs(1,0);
	if(poss || v[1].size() == 0){
		cout << "Impossible";
		return 0;
	}
	rep(0,v[f].size() - 1,i){
		m = -1000000005;
		if(v[f][i] != pf){
			calc(v[f][i],f);
			val.push_back(m);
		}
	}
	sort(val.begin(),val.end());
	ll tmp = val.size();
	(tmp > 1) ? cout <<  val[tmp - 1] + val[tmp - 2] : cout << "Impossible";
}