http://codeforces.com/contest/743/problem/D
如果我们知道mx[1]表示以1为根节点的子树中，点权值的最大和是多少（可能是整颗树，就是包括了自己）。那么，就可以O(n)扫一次各个点，对于每个点的儿子。
选出最大的两个mx[son]，更新答案即可。（注意这个节点只有1个或者没有儿子，就要是-inf）
那么怎么得到这个mx[]呢？
可以知道mx[father] = max(所有的mx[son])
最后还要看看是否能选择整个树，所以用dp[cur]表示以cur为根的树的所有点券之和。
然后就能dfs算出mx[]和dp[]。然后O(n)扫一次就好。
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
typedef long long int LL;
const LL inf = 1e16L; #include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
const int maxn = 2e5 + ;
int a[maxn];
struct node {
int u, v, w;
int tonext;
}e[maxn << ];
int first[maxn];
int num;
void add(int u, int v) {
++num;
e[num].u = u;
e[num].v = v;
e[num].tonext = first[u];
first[u] = num;
}
bool vis[maxn];
LL dp[maxn];
LL mx[maxn];
void init(int cur) {
dp[cur] = a[cur];
mx[cur] = -inf;
for (int i = first[cur]; i; i = e[i].tonext) {
int v = e[i].v;
if (vis[v]) continue;
vis[v] = true;
init(v);
dp[cur] += dp[v];
mx[cur] = max(mx[cur], mx[v]);
// mx[cur] = max(mx[cur], dp[v]);
}
mx[cur] = max(dp[cur], mx[cur]);
}
LL ans = -inf;
void dfs(int cur, int fa) {
LL mx1 = -inf, mx2 = -inf;
int t = ;
for (int i = first[cur]; i; i = e[i].tonext) {
int v = e[i].v;
if (fa == v) continue;
dfs(v, cur);
t++;
if (mx1 <= mx[v]) {
mx2 = mx1;
mx1 = mx[v];
} else if (mx2 <= mx[v]) {
mx2 = mx[v];
}
}
if (t == || t == ) return;
ans = max(ans, mx1 + mx2);
}
void work() {
int n;
scanf("%d", &n);
for (int i = ; i <= n; ++i) {
scanf("%d", &a[i]);
}
for (int i = ; i <= n - ; ++i) {
int u, v;
scanf("%d%d", &u, &v);
add(u, v);
add(v, u);
}
vis[] = true;
init();
// printf("%d\n", dp[6]);
// cout << mx[5] << endl;
memset(vis, , sizeof vis);
dfs(, );
if (ans <= -inf) {
cout << "Impossible" << endl;
} else cout << ans << endl;
} int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
work();
return ;
}