题解：P8625 [蓝桥杯 2015 省 B] 生命之树

· · 题解

题目大意

题目中讲到：_a,v_1,v_2,...,v_k,b 使得这个点列中的每个点都是 S 里面的元素，且序列中相邻两个点间有一条边相连。_

这意味着 S 为一个连通的集合，并且和要最大。即在一棵树中找到其的最大连通分量。

思路分析

算法：树形 dp。

我们不妨令 dp_u 表示：

以 u 为根子树的最大连通权值和。

那么 dp_u 的值就是只需在其儿子节点 dp_v 和自己本身的权值中取个较大值即可。

解题步骤

  1. 用 a_i 存储每个节点的权值并读入树的边。
  2. 通过 dfs 遍历此树。
  3. 在 dfs 的同时进行对 dp 数组的计算。
  4. 遍历结束，在 dp_1...n 中找到最大值，输出。

    代码实现

#include<bits/stdc++.h>
#define int long long//一定要开
using namespace std;
const int N=1e5+7,inf=1e18;
int n,a[N],dp[N];//dp[u]以u节点为根其子树的最大连通权值 
vector<int> g[N];
void dfs(int u,int fa){
    dp[u]=a[u];//初始化  最大值是根节点的权 
    for(auto v:g[u]){
        if(v==fa)continue ;
        dfs(v,u);
        dp[u]=max(dp[u],dp[u]+dp[v]);//状态转移  自己的最大值 和 自己加上子树的最大值 的较大值 
    }
}
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
        //存入树边 
    }
    dfs(1,-1);
    int ans=0;//注意：s可以为空集 此处不能将ans赋值为负无穷大 
    for(int i=1;i<=n;i++)ans=max(ans,dp[i]);
    cout<<ans;
    return 0;
}

注：十年 OI 一场空，不开 long long 见祖宗