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 + 20; int a[maxn]; struct node { int u, v, w; int tonext; }e[maxn << 1]; 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 = 0; 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 == 0 || t == 1) return; ans = max(ans, mx1 + mx2); } void work() { int n; scanf("%d", &n); for (int i = 1; i <= n; ++i) { scanf("%d", &a[i]); } for (int i = 1; i <= n - 1; ++i) { int u, v; scanf("%d%d", &u, &v); add(u, v); add(v, u); } vis[1] = true; init(1); // printf("%d ", dp[6]); // cout << mx[5] << endl; memset(vis, 0, sizeof vis); dfs(1, 0); 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 0; }