树形DP
WA点:注意要找的是非空集合,测一下边界数据就能发现这个WA点,也就是输入1 -5时答案是-5。
RE点:注意存的是双向边,要在给的数据范围上乘2。
#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<cmath> using namespace std; struct edge { int to; edge* next; }ee[32100],*e[16005]; int ecnt; int val[16005]; bool visited[16005]; int dp[16005][2]; void addedge(int u,int v) { ee[ecnt].to=v;ee[ecnt].next=e[u];e[u]=&ee[ecnt]; ecnt++; ee[ecnt].to=u;ee[ecnt].next=e[v];e[v]=&ee[ecnt]; ecnt++; } void dfs(int u) { visited[u]=true; int v,sum=0; bool f=false; edge *t; for(t=e[u];t;t=t->next) { v=t->to; if(!visited[v]) { dfs(v); if(dp[v][1]>0) sum+=dp[v][1]; if(!f||dp[v][0]>dp[u][0]) { dp[u][0]=dp[v][0]; f=true; } if(!f||dp[v][1]>dp[u][0]) { dp[u][0]=dp[v][1]; f=true; } } } dp[u][1]=sum+val[u]; if(!f) dp[u][0]=val[u]; return ; } int main() { int i,j,u,v,n; scanf("%d",&n); ecnt=0; memset(visited,false,sizeof(visited)); for(i=1;i<=n;++i) scanf("%d",&val[i]); for(i=1;i<n;++i) { scanf("%d %d",&u,&v); addedge(u,v); } dfs(1); printf("%d\n",max(dp[1][0],dp[1][1])); return 0; }