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

题目大意

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

这意味着

S

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

思路分析

算法：树形 dp。

我们不妨令

dp_u

表示：

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

那么

dp_u

的值就是只需在其儿子节点

dp_v

和自己本身的权值中取个较大值即可。

解题步骤

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

代码实现

CPP

#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 见祖宗~~

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

文章操作

题目大意

思路分析

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

解题步骤

代码实现

相关推荐

评论

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

文章操作

题目大意

思路分析

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

解题步骤

代码实现

相关推荐

评论

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