参考代码:
#include<bits/stdc++.h> using namespace std; struct node { int to; int next; }mp[100005]; int head[100005]; int cnt=0; void add(int a,int b) { mp[++cnt].to=b; mp[cnt].next=head[a]; head[a]=cnt; } int a[100005]; int dp[100005][5]; 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) { dfs(v,u); } } dp[fa][0]+=max(dp[u][1],dp[u][0]);//父节点不被邀请时,子节点可被邀请也可不被邀请 dp[fa][1]+=dp[u][0];//父节点被邀请子节点不能被邀请 } int main() { int n; cin>>n; for(int i=1;i<=n;i++) { cin>>dp[i][1]; } for(int i=1;i<n;i++) { int a,b; cin>>a>>b; add(a,b); add(b,a); } dfs(1,0); int ans=0; for(int i=0;i<=n;i++) { for(int j=0;j<=1;j++) { ans=max(ans,dp[i][j]); } } cout<<ans; return 0; }
0.0分
0 人评分
C语言程序设计教程(第三版)课后习题10.7 (C语言代码)浏览:967 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:584 |
C语言程序设计教程(第三版)课后习题6.6 (C语言代码)浏览:624 |
兰顿蚂蚁 (C++代码)浏览:1045 |
C语言训练-求1+2!+3!+...+N!的和 (C语言代码)浏览:787 |
C语言训练-自由落体问题 (C语言代码)浏览:615 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:589 |
C语言程序设计教程(第三版)课后习题10.3 (C语言代码)浏览:509 |
整除问题 (C语言代码)浏览:526 |
C语言训练-大、小写问题 (C语言代码)浏览:681 |