原題:

在X森林里，上帝創(chuàng)建了生命之樹。

他給每棵樹的每個(gè)節(jié)點(diǎn)（葉子也稱為一個(gè)節(jié)點(diǎn)）上，都標(biāo)了一個(gè)整數(shù)，代表這個(gè)點(diǎn)的和諧值。 上帝要在這棵樹內(nèi)選出一個(gè)非空節(jié)點(diǎn)集S，使得對(duì)于S中的任意兩個(gè)點(diǎn)a,b，都存在一個(gè)點(diǎn)列 {a, v1, v2, …, vk, b} 使得這個(gè)點(diǎn)列中的每個(gè)點(diǎn)都是S里面的元素，且序列中相鄰兩個(gè)點(diǎn)間有一條邊相連。 在這個(gè)前提下，上帝要使得S中的點(diǎn)所對(duì)應(yīng)的整數(shù)的和盡量大。 這個(gè)最大的和就是上帝給生命之樹的評(píng)分。

經(jīng)過(guò)atm的努力，他已經(jīng)知道了上帝給每棵樹上每個(gè)節(jié)點(diǎn)上的整數(shù)。但是由于 atm 不擅長(zhǎng)計(jì)算，他不知道怎樣有效的求評(píng)分。他需要你為他寫一個(gè)程序來(lái)計(jì)算一棵樹的分?jǐn)?shù)。

「輸入格式」 第一行一個(gè)整數(shù) n 表示這棵樹有 n 個(gè)節(jié)點(diǎn)。 第二行 n 個(gè)整數(shù)，依次表示每個(gè)節(jié)點(diǎn)的評(píng)分。 接下來(lái) n-1 行，每行 2 個(gè)整數(shù) u, v，表示存在一條 u 到 v 的邊。由于這是一棵樹，所以是不存在環(huán)的。

「輸出格式」 輸出一行一個(gè)數(shù)，表示上帝給這棵樹的分?jǐn)?shù)。

「樣例輸入」 5 1 -2 -3 4 5 4 2 3 1 1 2 2 5

「樣例輸出」 8 「數(shù)據(jù)范圍」 對(duì)于 30% 的數(shù)據(jù)，n <= 10 對(duì)于 100% 的數(shù)據(jù)，0 < n <= 10^5, 每個(gè)節(jié)點(diǎn)的評(píng)分的絕對(duì)值不超過(guò) 10^6 。

資源約定： 峰值內(nèi)存消耗 < 256M CPU消耗 < 3000ms

簡(jiǎn)單樹形dfs