解题思路:树形dp,查找最大子树和
注意事项:集合可以为空,也就是说如果树中节点全小于0则为空集输出0
参考代码:
#include<bits/stdc++.h> using namespace std; struct node { int to; int w; int next; }mp[1000005]; int head[500005]; int cnt=0; //int a[100005]; void add(int a,int b) { mp[++cnt].next=head[a]; mp[cnt].to=b; head[a]=cnt; } long long dp[500005]; void dfs(int u,int fa) { for(int i=head[u];i;i=mp[i].next) { int v; v=mp[i].to; if(v==fa)continue; dfs(v,u); } dp[fa]=max(dp[fa],dp[u]+dp[fa]); } int main() { int n; cin>>n; int num; for(int i=1;i<=n;i++) { cin>>dp[i]; } for(int i=1;i<n;i++) { int a,b,c; cin>>a>>b; add(a,b); add(b,a); } dfs(1,0); long long ans=-2147483647; for(int i=1;i<=n;i++) { ans=max(dp[i],ans); } if(ans<0)ans=0; printf("%lld",ans); }
0.0分
0 人评分
剔除相关数 (C语言代码)浏览:1013 |
C语言训练-素数问题 (C语言代码)浏览:995 |
九宫重排 (C++代码)浏览:2160 |
简单的a+b (C++语言代码)浏览:853 |
WU-复数求和 (C++代码)浏览:2008 |
C语言训练-求s=a+aa+aaa+aaaa+aa...a的值 (C语言代码)浏览:691 |
Hello, world! (C++代码)浏览:1744 |
DNA (C语言描述,蓝桥杯)浏览:1553 |
1157题解浏览:714 |
C语言程序设计教程(第三版)课后习题5.4 (C语言代码)浏览:790 |