人品问题
Description
網(wǎng)上出現(xiàn)了一種高科技產(chǎn)品——人品測試器。只要你把你的真實(shí)姓名輸入進(jìn)去，系統(tǒng)將自動(dòng)輸出你的人品指數(shù)。yzx不相信自己的人品為0。經(jīng)過了許多研究后，yzx得出了一個(gè)更為科學(xué)的人品計(jì)算方法。這種方法的理論依據(jù)是一個(gè)非常重要的結(jié)論：人品具有遺傳性。因此，一個(gè)人的人品完全由他的祖先決定。yzx提出的人品計(jì)算方法相當(dāng)簡單，只需要將測試對(duì)象的k個(gè)祖先的人品指數(shù)（可能為負(fù)數(shù)）加起來即可。選擇哪k個(gè)祖先可以由測試者自己決定，但必須要滿足這個(gè)要求：如果除自己的父母之外的某個(gè)祖先被選了，那么他的下一代必需要選（不允許跳過某一代選擇更遠(yuǎn)的祖先，否則將失去遺傳的意義）。
非常不幸的是，yzx測試了若干次，他的人品值仍然不能為一個(gè)正數(shù)。現(xiàn)在yzx需要你幫助他找到選擇祖先的最優(yōu)方案，使得他的人品值最大。
Input
第一行是兩個(gè)用空格隔開的正整數(shù)n和k，其中n代表yzx已知的家譜中共有多少人（包括yzx本身在內(nèi)），k的意義參見問題描述。
第二行有n-1個(gè)用空格隔開的整數(shù)（可能為負(fù)），這些數(shù)的絕對(duì)值在2^15以內(nèi)。其中，第i個(gè)數(shù)表示編號(hào)為i+1的人的人品值。我們規(guī)定，編號(hào)為1的人是yzx。
接下來n行每行有兩個(gè)用空格隔開的數(shù)，其中第i行的兩個(gè)數(shù)分別表示第i個(gè)人的父親和母親的編號(hào)。如果某個(gè)人的父親或母親不在這個(gè)家譜內(nèi)，則在表示他的父親或母親的編號(hào)時(shí)用0代替。
除yzx以外的所有人都是yzx的祖先，他們都會(huì)作為父親或母親被描述到。每個(gè)人都不可能同時(shí)作為多個(gè)人的父親或者是母親。
Output
一個(gè)整數(shù)，表示yzx能夠得到的最大人品值。
Sample Input
6 3
-2 3 -2 3 -1
2 3
4 5
0 6
0 0
0 0
0 0
Sample Output
4
樣例說明下圖顯示了輸入樣例所描述的家譜圖。括號(hào)里的數(shù)表示的是該人的人品值。
顯然，選擇祖先2、3、5能使yzx的人品值達(dá)到最大。這個(gè)最大值為4，表示yzx能夠得到的最大人品值。
Data Constraint
50%的數(shù)據(jù)，n<=10。
100%的數(shù)據(jù)，n<=100。
.
.
.
.
.
.
分析
樹形DP
.
.
.
.
.
程序：
轉(zhuǎn)載于:https://www.cnblogs.com/YYC-0304/p/10458946.html
總結(jié)
