有一棵包含 $N$ 個節點的樹 $T=(V,E)$。每個節點上寫有一個整數，注意這個整數可以為負數。我們希望找出 $T$ 的兩個子圖 $T_a=(V_a,E_a)$ 和 $T_b=(V_b,E_b)$，滿足以下條件。

• $V_a\ne\varnothing,\quad V_b\ne\varnothing$

• $T_a$ 和 $T_b$ 分別都是連通圖。

• $V_a\cap V_b=\varnothing$

• $E$ 中不存在連接 $V_a$ 中節點與 $V_b$ 中節點的邊。

• $V_a$ 中所有節點上的整數之和，加上 $V_b$ 中所有節點上的整數之和，必須盡可能大。

考慮下圖中的例子： $T=(\{0,1,2,3,4,5,6\},\{(0,1),(0,2),(2,3),(2,4),(4,6),(5,6)\})$.

節點上方的數字是節點編號，節點內部的數字是節點上的值。滿足上述條件的 $T_a,T_b$ 可能有多種選擇。取 $V_a=\{0,2,3\}$、$V_b=\{5,6\}$ 時，總和為 $\{3+(-1)+4\}+\{5+3\}=14$，達到最大。雖然還有其他選擇，但無法得到大於 $14$ 的值。

你需要實作以下函式。

long long findSum( int N, int C[], int Node1[], int Node2[] );

該函式恰好被呼叫一次。輸入透過參數傳入，傳回值就是本題答案。$N$ 表示節點個數，節點編號為 $0$ 到 $N-1$。對於 $0\le i\le N-1$，C[i] 表示節點 $i$ 上的整數。對於 $0\le i\le N-2$，節點 Node1[i] 與 Node2[i] 之間有一條邊。

實作細節

你必須恰好提交一個名為 tree.cpp 的檔案，其中實作以下函式。

long long findSum( int N, int C[], int Node1[], int Node2[] );

該函式應按上述說明運作。你可以定義其他函式供內部使用。提交的程式碼不得進行輸入輸出，也不得存取其他檔案。

範例評測程式

提供的評測程式按照以下格式讀取輸入。

• 第 1 行： $N$

• 第 2 行：$N$ 個整數 $C_0,C_1,\ldots,C_{N-1}$，依次表示各節點上的值。

• 接下來 $N-1$ 行：兩個整數 $a,b$，表示節點 $a$ 與 $b$ 之間有一條邊。

請注意，如果輸入某行最後一個數字字元之後還有空格或其他字元，評測程式可能無法正常運作。

評測程式輸出你的 findSum() 函式的傳回值。

資料範圍

• $-10^9\le C_i\le10^9$

• $3\le N\le500,000$

子任務

1. (7 分) $N\le20$

2. (19 分) $N\le5000$

3. (74 分) 無額外限制。

範例

輸入格式 1

7
3 -5 -1 4 2 5 3
0 1
0 2
2 3
2 4
4 6
5 6

輸出格式 1

14