關於樹形DP，我這今天早上才弄懂了一道題。之前一直覺得這是什麼特別高端的東西，但是就這道題而言，無非就是一個數塔的操作放在樹上了。
題目大意：學校要開一個聚會。學校的教職工之間有上下級關系，為了讓所有人開心，宴會組織者決定不會同時邀請一個人和他的上級（這讓我想起我們昨天晚上聚餐李晔老師不來，她怕她來了我們放不開。。。。），對於每一個人，他能給聚會帶來的歡樂度有一個值，問組織者該邀請哪些人能夠使宴會的歡樂度達到最大值。
首先是DP的部分（也是很無聊的一部分）：每個參與者都有兩種狀態，一種是參加，一種是不參加。這個狀態的後續影響就是如果他參加了，他的直接上司和直接下屬都不能參加。我們可以用一個二維二態的數組來描述：dp[i][1]表示第i個參與者參加了，dp[i][0]表示第i個參與者沒有參加。狀態轉移方程就是dp[i][1]=dp[i][1]+dp[i-1][0]，dp[i][0]=dp[i][0]+Max(dp[i-1][0],dp[i-1][1])。這要是放在一個線性表上，同志們肯定都直接呵呵了。可所謂的樹形DP就是把這個簡單的操作放在樹上了。
樹的部分：之前很多大牛說圖論的題目，難就難在一個建圖。對這道題來說，DP是入門級的，很簡單。但是這個建圖讓我糾結了許久。。。代碼中是用靜態鏈表的操作完成了一個父節點下面所有子節點的記錄，對於一個子節點的操作完成之後，通過point[now].next指向下一個子節點，一直到point[now].next等於-1的時候，表示這個父節點下面所有的子節點已經遍歷完成。返回父節點，再去操作這個父節點的兄弟節點。在這一點上，就是很直白的深搜的操作了。
理解代碼的時候，個人建議把圖畫出來，再跟蹤代碼的數據，逐個去記錄。反正我就是這麼理解的。。。。。
[cpp] #include<stdio.h>
#include<string.h>
#define N 6005
struct node
{
int pa,son;
int next;
}point[N];//其實從這個結構體就可以看出很多東西，這就是一個靜態鏈表，在計算過程中遍歷一個節點的所有子節點的操作也是和鏈表完全相同的。不過我這都是後知後覺啊。
int dp[N][2],list[N],flag[N],value[N];
int pos;
int Max(int x,int y)
{
return x>y?x:y;
}
void add(int pa,int son)
{
point[pos].pa=pa;
point[pos].son=son;
point[pos].next=list[pa];//以靜態鏈表的形式存儲一個父節點下面所有的子節點。
list[pa]=pos++;
return ;
}
void dfs(int root)//這道題說起來是樹形DP，但是最沒有講的價值的就是這個DP。就是個入門級數塔的操作放在樹上了。
{
if(list[root]==-1)
{
dp[root][1]=value[root];
dp[root][0]=0;
return ;
}
int now=list[root];
dp[root][0]=0;
dp[root][1]=value[root];
while(now!=-1)
{
dfs(point[now].son);
dp[root][1]+=dp[point[now].son][0];//既然取了父節點的值，子節點的值就不能再取了。
dp[root][0]+=Max(dp[point[now].son][1],dp[point[now].son][0]);//父節點的值沒有取，子節點的值分取和不取兩種情況，取其中較大的那種情況。
now=point[now].next;//這個子節點計算過了，就要開始計算下一個子節點了。
}
return ;
}
int main()
{
int i,n;
while(scanf("%d",&n)!=EOF)
{
for(i=1;i<=n;i++)
scanf("%d",&value[i]);//記錄每一個點的值
int a,b;
pos=0;
memset(list,-1,sizeof(list));
memset(flag,0,sizeof(flag));
while(scanf("%d%d",&a,&b),a+b)
{
add(b,a);//將邊加入樹中
flag[a]=1;//記錄a有父節點，不可能是祖節點。
}
a=1;
while(flag[a]==1)
a++;//從a往後查，遇到的第一個flag[a]的值是-1的點，這就是大名鼎鼎的祖節點了。
dfs(a);
printf("%d\n",Max(dp[a][0],dp[a][1]));
}
return 0;
}
