hdu 1520 Anniversary party[树形dp]

?pid=1520

代码：

#include<iostream>#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#include<vector>#include<string>#include<queue>#include<deque>#include<stack>#include<map>#include<set>#define INF 0x7fffffff#define SUP 0x80000000#define mem(a,b) memset(a,b,sizeof(a))using namespace std;typedef long long LL;const int N=10007;int val[N];int gra[N][N],dp[N][2];int vis[N];void dfs(int u){vis[u]=1;dp[u][1]=val[u];int v;for(int i=1;i<=gra[u][0];i++){v=gra[u][i];if(vis[v]) continue;dfs(v);dp[u][0]+=max(dp[v][0],dp[v][1]);dp[u][1]+=dp[v][0];}}int main(){int n;while(scanf("%d",&n)==1){for(int i=1;i<=n;i++){scanf("%d",val+i);vis[i]=gra[i][0]=0;}int u,v;while(scanf("%d%d",&u,&v),u||v){gra[u][++gra[u][0]]=v;gra[v][++gra[v][0]]=u;}mem(dp,0);dfs(1);printf("%d\n",max(dp[1][0],dp[1][1]));}return 0;}

，将会错过更好的风景，保持一份平和，保持一份清醒。