袋鼠吃豬腳
pA 的袋鼠在無限次跳躍後來到一個盛產豬腳的城市,這個城市有 \(n\) 間超商和 \(n-1\) 條道路,每條道路連接兩間超商,且都可以雙向通行,並且保證任兩間超商之間可以經過有限條道路到達。此外,在第 \(i\) 座超商,總共有 \(w_i\) 隻豬腳。現在,袋鼠將從超商1出發去購買豬腳。當袋鼠在某一間超商時,她可以選擇要購買多少豬腳,因為袋鼠很想要吃豬腳,所以她只會選擇買下超商的所有豬腳或是完全不買。並且,袋鼠為了避免迷路,不會經過同一間超商兩次。最後,袋鼠希望自己每一次購買豬腳的數量都大於前一次購買豬腳的數量(第一次除外)。現在袋鼠想問問你,她最多可以在幾間超商購買豬腳呢?
Input
第 \(1\) 行有一個正整數 \(n\) 代表超商數量, \(1 \leq n \leq 2\times 10^5\)
第 \(2\) 行到第 \(n\) 行,每行有兩個正整數 \(u,v\) ,代表超商 \(u\) 和 \(v\) 之間有一條道路, \(1 \leq u,v \leq n\)
第 \(n+1\) 行有 \(n\) 個整數,第 \(i\) 個正整數代表 \(w_i\) ,意義如題序所述, \(\forall 1 \leq i \leq n, 1 \leq w_i \leq 10^9\)
Output
輸出一個正整數,代表袋鼠最多可以在幾間超商購買豬腳
Constraints
第 \(1\) 組測資, \(\forall (u,v),v=u+1\) 。 (\(20 \%\))
第 \(2\) 組測資, \(\forall (u,v),u=1\) 。 (\(10 \%\))
第 \(3\) 組測資, \(n \leq 5000\) 。 (\(30 \%\))
第 \(4\) 組測資,無特別限制。 (\(40 \%\))
Sample Input 1
6
1 2
4 3
2 5
1 3
6 2
9 5 1 2 1 9
Sample Output 1
2
Sample Input 2
9
1 2
7 8
6 7
3 4
8 9
2 3
4 5
5 6
7 2 1 10 8 7 7 2 7
Sample Output 2
3
Sample Input 3
7
1 7
1 2
1 6
1 5
1 4
1 3
2 5 8 2 3 7 10
Sample Output 3
2
Sample Input 4
1
1
Sample Output 4
1
Comments