题解 CF743D 【Chloe and pleasant prizes】
皎月半洒花
2019-02-24 19:09:29
一道不是很难的$DP$。
形式上，本文对“子树”和“连通块”不做区分。
我们思考，我们随便指定一个当根，那么我们考虑转移的时候是否需要跨出子树——其然是不需要的。因为我们最终的结果一定会是两棵不相交的最大的子树，所以我们直接令$1$为根。
那么就很显然了，我们只需要对每个$u$找出其子树内最大和次大的连通块，转移就好。我们令$dp[0]$作为最终答案，$dp[u]$记录子树内的最大连通块权值。那么当我们只访问了$u$的时候，记录一下我们是否已经计算过一颗子树，如果是就枚举另一颗子树并且不断更新当前的最大子树即可。
此处有一个小$trick$，即先更新$ans$后更新$dp[u]$，其作用是不言而喻的。
```cpp
#include <cstdio>
#include <iostream>
#define MAXN 300020
#define to(k) E[k].to
#define Fuck -23333666623336LL
using namespace std ;
struct Edge{
int to, next ;
}E[MAXN] ; int head[MAXN], cnt ;
long long N, base[MAXN], S[MAXN], dp[MAXN], A, B, i ;
inline void Add(int u, int v){
E[++ cnt].to = v, E[cnt].next = head[u], head[u] = cnt ;
E[++ cnt].to = u, E[cnt].next = head[v], head[v] = cnt ;
}
void work_on_dp(int now, int f){
S[now] = base[now] ;
for (int k = head[now] ; k ; k = E[k].next){
if (f == E[k].to) continue ;work_on_dp(to(k), now) ;
if (dp[now] > Fuck) dp[0] = max(dp[0], dp[now] + dp[to(k)]) ;
S[now] += S[to(k)], dp[now] = max(dp[now], dp[to(k)]) ;
}
if (now != 1) dp[now] = max(dp[now], S[now]) ;//dp[now]表示最大子树和（即只选取一颗子树，选取哪一棵）
}
int main(){
cin >> N ; fill(dp, dp + N + 2, Fuck) ;
for (i = 1 ; i <= N ; ++ i) scanf("%lld", &base[i]) ;
for (i = 1 ; i < N ; ++ i) scanf("%d%d", &A, &B), Add(A, B) ;
work_on_dp(1, 0) ; (dp[0] > Fuck ? cout << dp[0] << endl : cout << "Impossible" << endl) ; return 0 ;
}
```