题目地址：http://codeforces.com/contest/743/problem/D 题意：告诉你一个树每个节点的价值，让你求出不相交的两个子树的价值和最大。 思路：树形dp入门。用vector存树的信息，每次遍历的时候不走回头路，dp数组去存这个节点下最大的子树价值和。
#include <iostream> #include <cstring> #include <string> #include <queue> #include <vector> #include <map> #include <set> #include <stack> #include <cmath> #include <cstdio> #include <algorithm> #define LL long long #define N 200010 #define M 50010 #define inf 0x3f3f3f3f3f3f3f3f using namespace std; const LL mod = 1e9 + 7; const double eps = 1e-9; vector<LL> tree[N]; LL dp[N], val[N]; LL ans; void dfs(int u, int pre) { for (int i = 0; i < tree[u].size(); i++) { int v = tree[u][i]; if (v == pre) { continue; } dfs(v, u); val[u] += val[v]; if (dp[u] != -inf) { ans = max(ans, dp[u] + dp[v]); } dp[u] = max(dp[u], dp[v]); } dp[u] = max(dp[u], val[u]); } int main() { cin.sync_with_stdio(false); LL n, u, v; while (cin >> n) { ans = -inf; for (int i = 1; i <= n; i++) { cin >> val[i]; dp[i] = -inf; tree[i].clear(); } for (int i = 1; i < n; i++) { cin >> u >> v; tree[u].push_back(v); tree[v].push_back(u); } dfs(1, -1); if (ans == -inf) { cout << "Impossible" << endl; } else { cout << ans << endl; } } return 0; }