Thallium54

Codeforces 743D - Chloe and pleasant prizes 题解

DFS 动态规划 题解

Good DFS problem.

题解 #

我们需要用 DFS 计算sumvsum_v——vv的子树里所有数的和，以及m1vm1_v 和 m2vm2_v——v 的子树里所有的sumsum里的最大和次大值 (不包括sumvsum_v). 计算完之后更新答案。具体实现可以看代码，挺好理解的。

Code #

#include <bits/stdc++.h>
 
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define fore(i, l, r) for (int i = (int)(l); i <= (int)(r); ++i)
#define ford(i, n) for (int i = (int)(n)-1; i >= 0; --i)
#define pb push_back
#define ms(a, x) memset(a, x, sizeof(a))
#define F first
#define S second
#define endl '\n'
using namespace std;
 
typedef long long ll;
const ll INF = 1e18+1;
typedef pair<int, int> pii;
 
const int N=2e5+5;
vector<int> G[N];
ll a[N],sum[N],mx[N];
 
ll ans=-INF;
void dfs1(int v,int p){
    sum[v]=a[v];
    mx[v]=-INF;
    ll m1=-INF,m2=-INF;
    for(auto it:G[v]){
        if(it==p) continue;
        dfs1(it,v);
        sum[v]+=sum[it];
        mx[v]=max(mx[v],mx[it]);
        ll val=mx[it];
        if(val>m1) swap(m1,val);
        if(val>m2) swap(m2,val);
    }
    if(m2> -INF) ans=max(ans,m1+m2);
    mx[v]=max(mx[v],sum[v]);
    return;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
	int n;
    cin>>n;
    for1(i,n){
        cin>>a[i];
    }
    forn(i,n-1){
        int u,v;
        cin>>u>>v;
        G[u].emplace_back(v);
        G[v].emplace_back(u);
    }
    dfs1(1,1);
    if(ans==-INF) cout<<"Impossible";
    else cout<<ans;
    return 0;
}