Ural 州立大學(xué)的校長(zhǎng)正在籌備學(xué)校的 8080 周年紀(jì)念聚會(huì)。由于學(xué)校的職員有不同的職務(wù)級(jí)別，可以構(gòu)成一棵以校長(zhǎng)為根的人事關(guān)系樹(shù)。每個(gè)資源都有一個(gè)唯一的整數(shù)編號(hào)，從 1 到 N 編號(hào)，且對(duì)應(yīng)一個(gè)參加聚會(huì)所獲得的歡樂(lè)度。為使每個(gè)職員都感到快樂(lè)，校長(zhǎng)設(shè)法使每個(gè)職員和其直接上司不會(huì)同時(shí)參加聚會(huì)。

你的任務(wù)是設(shè)計(jì)一份參加聚會(huì)者的名單，使總歡樂(lè)度最高。

第一行是一個(gè)整數(shù) N；

接下來(lái) N 行對(duì)應(yīng) N 個(gè)職員的歡樂(lè)度，第 i 行的一個(gè)整數(shù)為第 i 個(gè)職員的歡樂(lè)度 p_i ；

接著是學(xué)校的人事關(guān)系樹(shù)，每一行格式為 L K ，表示第 K 個(gè)職員是第 L 個(gè)職員的直接上司，輸入以0 0 結(jié)束。

數(shù)據(jù)范圍與提示：

對(duì)于 100% 的數(shù)據(jù)，1≤N≤6000,?128≤p_i≤127。

信息學(xué)一本通 動(dòng)態(tài)規(guī)劃