http://codeforces.com/problemset/problem/743/D
题意：求最大两个的不相交子树的点权和，如果没有两个不相交子树，那么输出Impossible。
思路：之前好像也做过这种类型的题目啊，知道是树形DP，但是不知道怎么保证两个不相交。看别人代码之后，
在DFS回溯的时候，
void dfs(int u, int fa) {
sum[u] = w[u];
for(int i = head[u]; ~i; i = edge[i].nxt) {
int v = edge[i].v;
if(v == fa) continue;
dfs(v, u);
sum[u] += sum[v];
if(dp[u] > -INF) ans = max(ans, dp[u] + dp[v]);
dp[u] = max(dp[u], dp[v]);
}
dp[u] = max(dp[u], sum[u]);
}
先执行 if 语句的话，可以保证只有以 u 结点为根的时候，它的子树有两个或两个以上，否则就不会更新 ans 了。并且这个时候dp【u】还只是目前扫过的一个子树的最大权值和，再加上一个次大的dp【v】，这样就可以保证是最大的两个不相交子树的权值和了。遍历完后dp【u】一定是以 u 为根的所有子树的最大权值和，再和 sum【u】更新是否要包含u这个节点的权值。
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
#include <queue>
#include <vector>
using namespace std;
#define N 200010
typedef long long LL;
const LL INF = 1LL<<;
struct node
{
int v, nxt;
}edge[N*];
LL dp[N], sum[N], w[N], head[N], tot, ans; void add(int u, int v) {
edge[tot].v = v; edge[tot].nxt = head[u]; head[u] = tot++;
} void dfs(int u, int fa) {
sum[u] = w[u];
for(int i = head[u]; ~i; i = edge[i].nxt) {
int v = edge[i].v;
if(v == fa) continue;
dfs(v, u);
sum[u] += sum[v];
if(dp[u] > -INF) ans = max(ans, dp[u] + dp[v]);
dp[u] = max(dp[u], dp[v]);
}
dp[u] = max(dp[u], sum[u]);
} int main()
{
int n;
cin >> n;
memset(head, -, sizeof(head));
for(int i = ; i <= n; i++) cin >> w[i];
for(int i = ; i < n; i++) {
int u, v;
cin >> u >> v;
add(u, v); add(v, u);
}
ans = -INF;
for(int i = ; i <= n; i++) dp[i] = -INF;
dfs(, -);
if(ans <= -INF) puts("Impossible");
else cout << ans << endl;
return ;
}