問題文

頂点に 1, 2, \dots, N の番号が付いた、頂点 1 を根とする N 頂点の根付き木があります。i 番目の辺 (1 ≤ i ≤ N - 1) は頂点 U_i と頂点 V_i を結んでいます。

木の各頂点は白か黒で塗られており、頂点 i (1 ≤ i ≤ N) は A_i = 0 のとき白で、A_i = 1 のとき黒で塗られています。

木を黒くしたい黒木さんは、以下の操作を 0 回以上の任意の回数行って、黒で塗られている頂点の数を最大化します。

• 葉である頂点 x を 1 つ選び、根から x までのパスに含まれる頂点 (両端を含む) の色を反転させる (白で塗られている場合は黒に、黒で塗られている場合は白に塗り直す)。

黒木さんは何個の頂点が黒に塗られた木を得ることができるでしょうか？

制約

• 入力はすべて整数
• 2 \leq N \leq 10^5
• 0 \leq A_i \leq 1 (1 ≤ i ≤ N)
• 1 \leq U_i, V_i \leq N (1 ≤ i ≤ N - 1)
• 与えられるグラフは木である

入力例 1

5
1 0 0 1 0
1 2
1 3
3 4
3 5

出力例 1

5

以下のように操作をすると頂点をすべて黒で塗られた状態にすることができます。

1. 頂点 2 を選ぶ。これによって頂点 1 は白に、頂点 2 は黒になる。
2. 頂点 5 を選ぶ。これによって頂点 1 は黒に、頂点 3 は黒に、頂点 5 は黒になる。

入力例 2

6
1 1 0 0 1 0
3 1
2 5
1 2
4 1
2 6

出力例 2

5

入力例 3

9
1 0 1 0 1 0 1 0 1
2 9
1 2
6 9
3 8
4 5
5 9
2 8
7 8

出力例 3

6