JOI 發電廠有 $N$ 個基地，編號為 $1$ 至 $N$。這些基地由 $N-1$ 條電線連接。第 $i$ 條電線（$1 \le i \le N-1$）雙向連接基地 $A_i$ 和基地 $B_i$。沿著一些電線，可以從任何基地前往任何其他基地。

JOI 發電廠的每個基地至多有一部發電機。每部發電機都有一個開關。最初，所有發電機的開關都處於關閉狀態。你是 JOI 發電廠的廠長，可以選擇一些發電機，並將它們的開關打開，也可以一部都不選。發電機有以下性質。

• 假設基地 $x,y,z$ 都有發電機，並且可以依序從基地 $x$ 前往基地 $y$，再從基地 $y$ 前往基地 $z$，途中不會重複經過同一條電線。如果基地 $x$ 和基地 $z$ 的發電機開關都打開，基地 $y$ 的發電機就會損壞。
• 當一部發電機的開關打開且未損壞時，它就會運作。

最後，你會從運作中的發電機獲得報酬。每部運作中的發電機可獲得 $1$ 日圓。不過，你也必須支付損壞發電機的維修費用，每部損壞的發電機須支付 $1$ 日圓。報酬總額減去維修費用總額，就是你的利潤。

請寫一個程式，給定基地與電線的配置以及發電機的資訊，計算你能獲得的最大利潤。

輸入格式

從標準輸入讀取以下資料。

$$ \begin{array}{ll} N \\ A_1 & B_1 \\ \vdots \\ A_{N-1} & B_{N-1} \\ S \end{array} $$

其中，$S$ 是長度為 $N$ 的字串，表示各基地的發電機資訊。$S$ 的每個字元都是 0 或 1。第 $i$ 個字元（$1 \le i \le N$）描述基地 $i$ 的發電機：若基地 $i$ 沒有發電機，該字元為 0；若基地 $i$ 有發電機，該字元為 1。

輸出格式

向標準輸出寫出一行，包含選擇一些發電機並將其開關全部打開時，你能獲得的最大利潤。

資料範圍

• $1 \le N \le 200\,000$。
• $1 \le A_i \le N$（$1 \le i \le N-1$）。
• $1 \le B_i \le N$（$1 \le i \le N-1$）。
• $A_i \ne B_i$（$1 \le i \le N-1$）。
• 沿著一些電線，可以從任何基地前往任何其他基地。
• $S$ 是長度為 $N$、由 0 和 1 組成的字串。
• $S$ 至少包含一個 1。

子任務

1. （6 分）$N \le 16$。
2. （41 分）$N \le 2\,000$。
3. （53 分）沒有額外限制。

範例

輸入格式 1

6
2 3
4 3
1 3
3 5
6 2
110011

輸出格式 1

3

說明

在這個範例中，基地 $1,2,5,6$ 有發電機。

如果將基地 $1,2,5$ 的開關打開，這三個基地的發電機都會運作，你會獲得 $3$ 日圓。由於不必支付維修費用，利潤就是 $3$ 日圓。這是能獲得的最大利潤，因此輸出 $3$。

另一方面，如果將基地 $1,5,6$ 的開關打開，基地 $2$ 的發電機會損壞，基地 $1,5,6$ 的發電機則會運作。你會獲得 $3$ 日圓，並支付 $1$ 日圓維修費用，所以利潤為 $2$ 日圓。

如果將基地 $1,2,5,6$ 的開關打開，基地 $2$ 的發電機會損壞，基地 $1,5,6$ 的發電機則會運作。你會獲得 $3$ 日圓，並支付 $1$ 日圓維修費用，所以利潤為 $2$ 日圓。

輸入格式 2

8
1 2
3 5
6 4
4 5
5 2
7 2
2 8
11111111

輸出格式 2

3

輸入格式 3

16
7 10
5 11
9 4
14 12
2 11
14 16
4 2
1 13
11 3
7 1
15 9
2 1
11 6
14 9
8 9
0111111001001110

輸出格式 3

5