hdoj1520（入门树形dp）
题目链接：https://vjudge.net/problem/HDU-1520
题意：和luogu那道没有上司的舞会一样的题，给定一棵带点权的树，父结点和子结点不能同时选，问怎么选使得权值和最大，求最大值即可。
思路：最近开始肝树形dp，从入门题开始QAQ，加油！
用dp[u][0]表示结点u不选，dp[u][1]表示选，vi是结点u的子结点，那么：
dp[u][0]=sum(max(dp[vi][0],dp[vi][1]))
dp[u][1]=val[u]+sum(dp[vi][0])
一次dfs就ok了，结果为max(dp[root][0],dp[root][1])，root要自己找。
AC代码：
#include<cstdio> #include<algorithm> using namespace std; const int maxn=6005; int n,cnt,head[maxn],val[maxn],indeg[maxn],dp[maxn][2]; struct node{ int v,nex; }edge[maxn]; void adde(int u,int v){ edge[++cnt].v=v; edge[cnt].nex=head[u]; head[u]=cnt; } void dfs(int u){ dp[u][1]=val[u]; for(int i=head[u];i;i=edge[i].nex){ int v=edge[i].v; dfs(v); dp[u][0]+=max(dp[v][0],dp[v][1]); dp[u][1]+=dp[v][0]; } } int main(){ while(~scanf("%d",&n)){ cnt=0; for(int i=1;i<=n;++i){ scanf("%d",&val[i]); head[i]=0,indeg[i]=0,dp[i][0]=0; } int a,b; while(scanf("%d%d",&a,&b),a&&b){ indeg[a]=1; adde(b,a); } int root; for(int i=1;i<=n;++i) if(!indeg[i]){ root=i; break; } dfs(root); printf("%d ",max(dp[root][0],dp[root][1])); } return 0; }