[蓝桥杯][2015年第六届真题]生命之树
2021/4/11 10:25:32
本文主要是介绍[蓝桥杯][2015年第六届真题]生命之树,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
最大子段和的树上扩展。
状态表示:
\(f[u]\):在以\(u\)为根的子树中包含u的所有连通块中的权值的最大值。
状态转移:
如果子树中存在权值和为正的连通块,则包含上该子树,否则丢弃。
\(s_1,s_2,\cdots,s_k\)是\(u\)的孩子。
const int N=1e5+10; vector<int> g[N]; LL f[N]; int w[N]; int n; void dfs(int u,int fa) { f[u]=w[u]; for(int i=0;i<g[u].size();i++) { int j=g[u][i]; if(j == fa) continue; dfs(j,u); f[u]+=max(0LL,f[j]); } } int main() { cin>>n; for(int i=1;i<=n;i++) cin>>w[i]; for(int i=0;i<n-1;i++) { int a,b; cin>>a>>b; g[a].pb(b); g[b].pb(a); } dfs(1,-1); LL res=0; for(int i=1;i<=n;i++) res=max(res,f[i]); cout<<res<<endl; //system("pause"); return 0; }
这篇关于[蓝桥杯][2015年第六届真题]生命之树的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-29DataGrip使用ssh连接数据库的操作流程
- 2024-05-28SpringBoot3.2更新声明!
- 2024-05-28中外程序员到底有啥区别?
- 2024-05-25外企也半夜发布上线吗?
- 2024-05-24鸿蒙原生应用再新丁!芒果TV 入局鸿蒙
- 2024-05-22基本概念
- 2024-05-22检索数据
- 2024-05-22排序数据
- 2024-05-22基础过滤数据
- 2024-05-22通过逻辑操作符过滤数据