權值均為不超過1000的正整數。

樹形動態規劃

建立樹

其實就是儲存圖，有矩陣和鏈表。我這里用的是鏈式前向星，儲存的圖的思路是以每個點為起點，然后用head[i]儲存以i為起點的一條邊，通過鏈式結構遍歷所有邊。具體操作一個是邊結構，包含終點，和下一條邊的位置，另一個是添加函數，完成儲存終點，鏈式結構，指定新起始邊的任務。注意一條邊是屬于兩條邊的。

動態規劃

類似于最大獨立子集問題

子問題 以i為根節點的子樹權值和最大值

遞歸表達式    dp[x][0]+=max2(dp[k][0],dp[k][1]);（0不取x，1取x）                        dp[x][1]+=dp[k][0];

沒有重疊子問題，從葉開始只要算一遍。

#include<stdio.h>#define max2(a,b) a>b?a:b#define min2(a,b) a<b?a:b#define Max_ 100010int M=0;int dp[Max_][2];int head[Max_];struct edge{int to;int next;}e[Max_*2];void add(int v, int u){e[M].to=v;e[M].next=head[u];head[u]=M++;e[M].to=u;e[M].next=head[v];head[v]=M++;}void dfs(int x,int v){int i,k;for(i=head[x];i!=-1;i=e[i].next){    k=e[i].to;    if(k==v)continue;    dfs(k,x);    dp[x][0]+=max2(dp[k][0],dp[k][1]);    dp[x][1]+=dp[k][0];}}int main(){int n,i,u,v;scanf("%d",&n);memset(head,-1,sizeof(head));memset(dp,0,sizeof(dp));for(i=1;i<=n;i++){    scanf("%d",&dp[i][1]);}for(i=1;i<=n-1;i++){    scanf("%d%d",&u,&v);    add(u,v);}dfs(1,-1);PRintf("%d",max2(dp[1][1],dp[1][0]));return 0;}