题意:
给n点的树,每个点都有点值,如果根节点去了舞会,他的子节点就不会去。
问最大值
思路:
点值负数的变成0,统计子节点有多少值加在根节点不去的数组,根节点去的数组分开,从下往上计算,最后总根算一下去还是不去哪个大
#include<bits/stdc++.h> using namespace std; #define ll long long #define il inline #define it register int #define inf 0x3f3f3f3f #define lowbit(x) (x)&(-x) #define mem(a,b) memset(a,b,sizeof(a)) #define mod 1000000007 const int maxn=6010; struct node{ int to,next; }a[maxn<<1]; int n,s,cnt,tot,head[maxn],w[maxn],vis[maxn]; int dp[maxn][3]; il void add(int u,int v){ a[tot].next=head[u]; a[tot].to=v;head[u]=tot++; } void dfs(int u,int fa){ for(it i=head[u];i!=-1;i=a[i].next){ it v=a[i].to;if(v==fa){continue;} dfs(v,u); } it sum=0,sum2=0; for(it i=head[u];i!=-1;i=a[i].next){ it v=a[i].to;if(v==fa){continue;} sum+=dp[v][1];sum2+=dp[v][0]; } dp[u][0]=sum;dp[u][1]+=sum2; } int main(){ mem(head,-1); scanf("%d",&n);dp[0][0]=dp[0][1]=0; for(it i=1;i<=n;i++){ scanf("%d",&w[i]);if(w[i]<0){w[i]=0;} vis[i]=1;dp[i][1]=w[i];dp[i][0]=0; } for(it i=1;i<=n;i++){int v,u; scanf("%d%d",&v,&u);vis[v]=0; if(i==n){continue;} add(v,u);add(u,v); } it fa=-1; for(it i=1;i<=n;i++){ if(vis[i]){ fa=i;break; } } dfs(fa,0);//cout<<fa<<endl; printf("%d ",max(dp[fa][0],dp[fa][1])); return 0; }