题目链接：这里 题意 给你一棵树，让你找到其中的两个子树，使得子树和最大。 要求子树不相交。 题解 树形dp，dp[i]表示以i为根的子树里面存在的子树最大值是多少 记录最大值和次大值，俩加起来就是最大的。
//743 D #include <bits/stdc++.h> using namespace std; const int maxn = 2e5+7; const long long inf = 1e12; long long a[maxn], dp[maxn], flag, ans = -inf; int n; vector <int> E[maxn]; void dfs1(int x, int fa){ dp[x] = a[x]; for(int i = 0; i < E[x].size(); i++){ int v = E[x][i]; if(v == fa) continue; dfs1(v, x); dp[x] += dp[v]; } } void dfs2(int x, int fa){ long long mx1 = -inf, mx2 = -inf; for(int i = 0; i < E[x].size(); i++){ int v = E[x][i]; if(v == fa) continue; dfs2(v, x); if(dp[v] >= mx1){ mx2 = mx1; mx1 = dp[v]; } else if(dp[v] > mx2){ mx2 = dp[v]; } dp[x] = max(dp[x], dp[v]); } if(mx1 != -inf && mx2 != -inf){ ans = max(ans, mx1 + mx2); flag = 1; } } int main() { scanf("%d", &n); for(int i = 1; i <= n; i++) scanf("%lld", &a[i]); for(int i = 1; i < n; i++){ int u, v; scanf("%d%d", &u, &v); E[u].push_back(v); E[v].push_back(u); } dfs1(1, -1); dfs2(1, -1); if(!flag) puts("Impossible"); else printf("%lld\n", ans); }