Codeforces Round #384 (Div. 2) D

题目链接：

http://codeforces.com/problemset/problem/743/D

题意：

给你一棵树，让你找到其中的两个子树，使得子树和最大。
要求子树不相交。

思路：

树形dp，dp[i]表示以i为根的子树里面存在的子树最大值是多少
记录最大值和次大值，俩加起来就是最大的。---from acm贴吧

代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 #define MS(a) memset(a,0,sizeof(a))
 5 #define MP make_pair
 6 #define PB push_back
 7 const int INF = 0x3f3f3f3f;
 8 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
 9 inline ll read(){
10     ll x=0,f=1;char ch=getchar();
11     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
12     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
13     return x*f;
14 }
15 //////////////////////////////////////////////////////////////////////////
16 const int maxn = 2e5+10;
17 
18 ll w[maxn],dp[maxn],ans;
19 vector<int> g[maxn];
20 int n;
21 bool flag;
22 
23 void dfs(int u,int fa){
24     ll tmp = -INFLL;
25     dp[u] = -INFLL;
26 
27     for(int i=0; i<(int)g[u].size(); i++){
28         int v = g[u][i];
29         if(v == fa) continue;
30         dfs(v,u);
31         w[u] += w[v];
32         dp[u] = max(dp[u],dp[v]);
33         if(tmp!=-INFLL){
34             flag = 1;
35         }
36         ans = max(ans,tmp+dp[v]);
37         tmp = max(tmp,dp[v]);
38     }
39     dp[u] = max(dp[u],w[u]);
40 }
41 
42 int main(){
43     ans = -INFLL;
44     cin >> n;
45     for(int i=1; i<=n; i++)
46         cin >> w[i];
47     for(int i=1; i<n; i++){
48         int u,v; cin>>u>>v;
49         g[u].push_back(v);
50         g[v].push_back(u);
51     }
52 
53     dfs(1,-1);
54     if(!flag) puts("Impossible");
55     else cout << ans << endl;
56 
57     return 0;
58 }