树形DP入门题目。
树形DP说白了就是在搜索的时候动态规划。
只要你懂的深搜+动态规划，就能理解这个基础题了。
先直接搜索到最底层，然后一层一层动态规划，可以说有点像数塔。
dp[i][1],dp[i][0]代表取这个节点和不取这个节点，所以。
dp[i][1]+=dp[v][0] v是的子节点
dp[i][0]+=max(dp[v][1],dp[v][0])
初始的时候将最后一层叶子节点dp[i][1]赋值为相应值即可。
用邻接表 似乎更加的直观，速度自然是更加的快。
#include#include #include using namespace std; struct node{ int v,nxt; }e[12000]; int dp[6005][2],father[6005]; int num,head[6005]; int max(int a,int b){ return a>b a:b; } void add(int a,int b){ e[num].v=b;e[num].nxt=head[a];head[a]=num++; } void dfs(int n){ int i; for(i=head[n];i!=-1;i=e[i].nxt){ int v=e[i].v; if(father[v]==n){ dfs(v); dp[n][1]+=dp[v][0]; dp[n][0]+=max(dp[v][1],dp[v][0]); } } } int main() { int t; while(scanf("%d",&t)!=EOF){ memset(dp,0,sizeof(dp)); memset(head,-1,sizeof(head)); memset(father,0,sizeof(father)); num=0; int i; for(i=1;i<=t;i++) scanf("%d",&dp[i][1]); int root=1; int a,b; while(scanf("%d%d",&a,&b),a||b){ father[a]=b; add(b,a); if(father[b]==0) root=b; } dfs(root); printf("%d\n",dp[root][1]>dp[root][0] dp[root][1]:dp[root][0]); } return 0; }