题解 CF743D 【Chloe and pleasant prizes】

皎月半洒花 · 2019-02-24 19:09:29 · 题解

一道不是很难的DP。

形式上，本文对“子树”和“连通块”不做区分。

我们思考，我们随便指定一个当根，那么我们考虑转移的时候是否需要跨出子树——其然是不需要的。因为我们最终的结果一定会是两棵不相交的最大的子树，所以我们直接令1为根。

那么就很显然了，我们只需要对每个u找出其子树内最大和次大的连通块，转移就好。我们令dp[0]作为最终答案，dp[u]记录子树内的最大连通块权值。那么当我们只访问了u的时候，记录一下我们是否已经计算过一颗子树，如果是就枚举另一颗子树并且不断更新当前的最大子树即可。

此处有一个小trick，即先更新ans后更新dp[u]，其作用是不言而喻的。

#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 ;
}